Edited by Jeremy Gunawardena
Foreword by John M. Taylor
Foreword by Michael Atiyah
Publications of the Newton Institute (No. 11)
Publisher: Cambridge University Press
Print Publication Year: 1998
Online Publication Date:May 2010
Online ISBN:9780511662508
Hardback ISBN:9780521553445
Paperback ISBN:9780521055383
Chapter DOI: http://dx.doi.org/10.1017/CBO9780511662508.004
Subjects: Real and Complex Analysis, Differential and integral equations, dynamical systems and control theory
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
Introduction
It is a well-known fact that the boolean calculus is one of the mathematical foundations of electronic computers. This explains the important role of the boolean semiring in computer science. The aim of this paper is to present other semirings that occur in theoretical computer science. These semirings were named tropical semirings by Dominique Perrin in honour of the pioneering work of our Brazilian colleague and friend Imre Simon, but are also commonly known as (min, +)-semirings.
The aim of this paper is to present tropical semirings and to survey a few problems relevant to them. We shall try to give an updated status of the different questions, but detailed solutions of most problems would be too long and technical for this survey. They can be found in the other papers of this volume or in the relevant literature. We have tried to keep the paper selfcontained as much as possible. Thus, in principle, there are no prerequisites for reading this survey, apart from a standard mathematical background. However, it was clearly not possible to give a full exposition of the theory of automata within 20 pages. Therefore, suitable references will be given for readers who would like to pursue the subject further and join the tropical community.
The paper is organized as follows. The main definitions are introduced in Section 2. Two apparently disconnected applications of tropical semirings are presented: the Burnside type problems in group and semigroup theory in Section 3, and decidability problems in formal language theory in Section 4. The connection between the two problems is explained in Section 5. A conclusion section ends the paper.
pp. i-iv
pp. v-vi
pp. vii-viii
pp. ix-x
List of Participants : Read PDF
pp. xi-xii
An introduction to idempotency : Read PDF
pp. 1-49
pp. 50-69
Some automata-theoretic aspects of min-max-plus semirings : Read PDF
pp. 70-79
The finite power property for rational sets of a free group : Read PDF
pp. 80-87
The topological approach to the limitedness problem on distance automata : Read PDF
pp. 88-111
Types and dynamics in partially additive categories : Read PDF
pp. 112-132
Task resource models and (max, +) automata : Read PDF
pp. 133-144
Algebraic system analysis of timed Petri nets : Read PDF
pp. 145-170
Ergodic theorems for stochastic operators and discrete event networks. : Read PDF
pp. 171-208
Computational issues in recursive stochastic systems : Read PDF
pp. 209-230
Periodic points of nonexpansive maps : Read PDF
pp. 231-241
A system-theoretic approach for discrete-event control of manufacturing systems : Read PDF
pp. 242-261
Idempotent structures in the supervisory control of discrete event systems : Read PDF
pp. 262-281
Maxpolynomials and discrete-event dynamic systems : Read PDF
pp. 282-284
The Stochastic HJB equation and WKB method : Read PDF
pp. 285-302
The Lagrange problem from the point of view of idempotent analysis : Read PDF
pp. 303-321
A new differential equation for the dynamics of the Pareto sets : Read PDF
pp. 322-330
Duality between probability and optimization : Read PDF
pp. 331-353
Maslov optimization theory: topological aspect : Read PDF
pp. 354-382
Random particle methods in (max, +) optimization problems : Read PDF
pp. 383-391
The geometry of finite dimensional pseudomodules : Read PDF
pp. 392-405
A general linear max-plus solution technique : Read PDF
pp. 406-415
Axiomatics of thermodynamics and idempotent analysis : Read PDF
pp. 416-419
The correspondence principle for idempotent calculus and some computer applications : Read PDF
pp. 420-443