Book contents
- Frontmatter
- Contents
- Foreword
- Preface
- List of Participants
- An introduction to idempotency
- Tropical semirings
- Some automata-theoretic aspects of min-max-plus semirings
- The finite power property for rational sets of a free group
- The topological approach to the limitedness problem on distance automata
- Types and dynamics in partially additive categories
- Task resource models and (max, +) automata
- Algebraic system analysis of timed Petri nets
- Ergodic theorems for stochastic operators and discrete event networks.
- Computational issues in recursive stochastic systems
- Periodic points of nonexpansive maps
- A system-theoretic approach for discrete-event control of manufacturing systems
- Idempotent structures in the supervisory control of discrete event systems
- Maxpolynomials and discrete-event dynamic systems
- The Stochastic HJB equation and WKB method
- The Lagrange problem from the point of view of idempotent analysis
- A new differential equation for the dynamics of the Pareto sets
- Duality between probability and optimization
- Maslov optimization theory: topological aspect
- Random particle methods in (max, +) optimization problems
- The geometry of finite dimensional pseudomodules
- A general linear max-plus solution technique
- Axiomatics of thermodynamics and idempotent analysis
- The correspondence principle for idempotent calculus and some computer applications
Tropical semirings
Published online by Cambridge University Press: 05 May 2010
- Frontmatter
- Contents
- Foreword
- Preface
- List of Participants
- An introduction to idempotency
- Tropical semirings
- Some automata-theoretic aspects of min-max-plus semirings
- The finite power property for rational sets of a free group
- The topological approach to the limitedness problem on distance automata
- Types and dynamics in partially additive categories
- Task resource models and (max, +) automata
- Algebraic system analysis of timed Petri nets
- Ergodic theorems for stochastic operators and discrete event networks.
- Computational issues in recursive stochastic systems
- Periodic points of nonexpansive maps
- A system-theoretic approach for discrete-event control of manufacturing systems
- Idempotent structures in the supervisory control of discrete event systems
- Maxpolynomials and discrete-event dynamic systems
- The Stochastic HJB equation and WKB method
- The Lagrange problem from the point of view of idempotent analysis
- A new differential equation for the dynamics of the Pareto sets
- Duality between probability and optimization
- Maslov optimization theory: topological aspect
- Random particle methods in (max, +) optimization problems
- The geometry of finite dimensional pseudomodules
- A general linear max-plus solution technique
- Axiomatics of thermodynamics and idempotent analysis
- The correspondence principle for idempotent calculus and some computer applications
Summary
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.
- Type
- Chapter
- Information
- Idempotency , pp. 50 - 69Publisher: Cambridge University PressPrint publication year: 1998
- 63
- Cited by