The equality problem for rational series with multiplicities in the tropical semiring is undecidable. (English) Zbl 0834.68058

This paper is a corrected version of the author’s paper of the same title, which appeared in “Automata, Languages and Programming”, ICALP’92 Proceedings, Lect. Notes Comput. Sci. 623, 101-112 (1992).
The tropical semiring \({\mathcal M}\) has support \(N \cup \{ + \infty\}\) and operations \(a \oplus b = \min \{a,b\}\) and \(a \otimes b = a + b\). Let \({\mathcal Z} = (Z \cup \{ + \infty\}, \min, +)\) be the extension of \({\mathcal M}\) to arbitrary integers.
The main result of the paper states that the equality problem for \({\mathcal M}\)-rational series over an alphabet with at least two letters is undecidable. This answers one of the main open questions in the theory of the tropical semiring.
To prove his result the author shows the equivalence of decidability of the equality problems for \({\mathcal M}\) and \({\mathcal Z}\).
The decidability of the equality problem for \({\mathcal Z}\) is reduced to a restriction of Hilbert’s 10th problem. Some related undecidability and decidability results are proved.


68W30 Symbolic computation and algebraic computation
68Q45 Formal languages and automata
16Y60 Semirings
03B25 Decidability of theories and sets of sentences
Full Text: DOI