Series which are both max-plus and min-plus rational are unambiguous
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 1, p. 1-14

Consider partial maps Σ * with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.

DOI : https://doi.org/10.1051/ita:2005042
Classification:  68Q19,  68Q45,  68Q70
Keywords: rational series, automata, unambiguous, max-plus semiring, tropical semiring
@article{ITA_2006__40_1_1_0,
     author = {Lombardy, Sylvain and Mairesse, Jean},
     title = {Series which are both max-plus and min-plus rational are unambiguous},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     pages = {1-14},
     doi = {10.1051/ita:2005042},
     zbl = {1085.68081},
     mrnumber = {2197280},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2006__40_1_1_0}
}
Lombardy, Sylvain; Mairesse, Jean. Series which are both max-plus and min-plus rational are unambiguous. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 1, pp. 1-14. doi : 10.1051/ita:2005042. http://www.numdam.org/item/ITA_2006__40_1_1_0/

[1] F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronization and Linearity. John Wiley & Sons, New York (1992). | MR 1204266 | Zbl 0824.93003

[2] J. Berstel, Transductions and context-free languages. B.G. Teubner (1979). | MR 549481 | Zbl 0424.68040

[3] J. Berstel and C. Reutenauer, Rational Series and their Languages. Springer-Verlag (1988). | MR 971022 | Zbl 0668.68005

[4] A. Bonnier-Rigny and D. Krob, A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theoret. Comput. Sci. 134 (1994) 27-50. | Zbl 0823.68051

[5] S. Eilenberg, Automata, languages and machines, volume A. Academic Press, New York (1974). | MR 530382 | Zbl 0317.94045

[6] S. Gaubert and J. Mairesse, Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont. 44 (1999) 683-698. | Zbl 0955.68082

[7] K. Hashigushi, K. Ishiguro and S. Jimbo, Decidability of the equivalence problem for finitely ambiguous finance automata. Int. J. Algebra Comput. 12 (2002) 445-461. | Zbl 1007.68115

[8] J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co. (1979). | MR 645539 | Zbl 0426.68001

[9] I. Klimann, S. Lombardy, J. Mairesse and C. Prieur, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoret. Comput. Sci. 327 (2004) 349-373. | Zbl 1071.68035

[10] D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 4 (1994) 405-425. | Zbl 0834.68058

[11] D. Krob, Some consequences of a Fatou property of the tropical semiring. J. Pure Appl. Algebra 93 (1994) 231-249. | Zbl 0806.68083

[12] M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguist. 23 (1997) 269-311.

[13] P. Moller, Théorie algébrique des systèmes à événements discrets. Ph.D. thesis, École des Mines, Paris (1988).

[14] J. Sakarovitch, A construction on finite automata that has remained hidden. Theoret. Comput. Sci. 204 (1998) 205-231. | Zbl 0913.68137

[15] J. Sakarovitch, Éléments de théorie des automates. Vuibert Informatique, Paris (2003).

[16] A. Salomaa and M. Soittola, Automata Theoretic Aspects of Formal Powers Series. Springer-Verlag, Berlin (1978). | MR 483721 | Zbl 0377.68039

[17] M.-P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976/77) 243-259. | Zbl 0358.68129

[18] I. Simon, Recognizable sets with multiplicities in the tropical semiring, in Mathematical Foundations of Computer Science, Proc. 13th Symp., Lect. Notes Comput. Sci. 324 (1988) 107-120. | Zbl 0656.68086

[19] L. Stockmeyer and A. Meyer, Word problems requiring exponential time: preliminary report, in Fifth Annual ACM Symposium on Theory of Computing. Assoc. Comput. Mach., New York (1973) 1-9. | Zbl 0359.68050

[20] A. Weber, Finite-valued distance automata. Theoret. Comput. Sci. 134 (1994) 225-251. | Zbl 0938.68709