Recognizable sets with multiplicities in the tropical semiring. (English) Zbl 0656.68086

Mathematical foundations of computer science, Proc. 13th Symp., Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 107-120 (1988).
[For the entire collection see Zbl 0643.00024.]
Let us recall that the semi-ring \({\mathcal M}=({\mathbb{N}}\cup \{\infty \},Min,+)\) is called the tropical semi-ring. This paper is a survey of the theory of recognizable subsets of a free monoid with multiplicities in \({\mathcal M}\). The author reviews special different problems in finite automata and formal languages theories, where \({\mathcal M}\) plays an important role.
The paper begins with an overview of two classical equivalent decidability problems: the finite section and the limitedness problem for \({\mathcal M}\). The structure of the H. Leung algorithm for these problems is given. After that, the finite power problem in \(A^*\) is considered. Its link with the limitedness problem in \({\mathcal M}\) is precised. In the article’s following section, the connection between \({\mathcal M}\) and the non-deterministic complexity of finite automata is shown. Finally, the paper ends with a list of research questions and open problems.
Reviewer: D.Krob


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.


Zbl 0643.00024