×

Some consequences of a Fatou property of the tropical semiring. (English) Zbl 0806.68083

The tropical semiring \(\mathcal M\) is the semiring \(\mathbb{N} \cup \{+ \infty\}\) with sum \(\min(a,b)\) and product \(a + b\). It is shown that \(\mathbb{Z}_{\min} = \mathbb{Z} \cup \{+ \infty\}\) (with the same operations) is a Fatou extension of \(\mathcal M\); that is, each noncommutative rational series over \(\mathbb{Z}_{\min}\), which has coefficients in \(\mathcal M\), is rational over \(\mathcal M\). The equality problem for rational series over \(\mathcal M\) or \(\mathbb{Z}_{\min}\) is undecidable. However, it is decidable for a series which is both \(\mathbb{Z}_{\min}\)- and \(\mathbb{Z}_{\max}\)-rational. An application to the limitedness problem is also given.

MSC:

68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI HAL

References:

[1] Berstel, J.; Reutenauer, C., Rational series and their languages, (1986), Springer Berlin
[2] Eilenberg, S., Automata, languages and machines, Vol. A, (1974), Academic Press New York · Zbl 0317.94045
[3] Hashiguchi, K., Limitedness theorem on finite automata with distances functions, J. comput. system. sci., 24, 2, 233-244, (1982) · Zbl 0513.68051
[4] Krob, D., The equality problem for rational series with multiplicities in the tropical semiring is undecidable, (), 101-112
[5] Krob, D., The equality problem for rational series with multiplicities in the tropical semiring is undecidable, LITP technical report 92-63, (1992), Internat. J. Algebra and Comput., to appear.
[6] Ruich, W.; Salomaa, A., Semirings, automata, languages, (1986), Springer Berlin
[7] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer Berlin · Zbl 0377.68039
[8] Simon, I., Recognizable sets with multiplicities in the tropical semiring, (), 107-120
[9] Simon, I., The nondeterministic complexity of finite automata, (), 384-400
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.