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.
Mots clés : 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}, pages = {1--14}, publisher = {EDP-Sciences}, volume = {40}, number = {1}, year = {2006}, doi = {10.1051/ita:2005042}, mrnumber = {2197280}, zbl = {1085.68081}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2005042/} }
TY - JOUR AU - Lombardy, Sylvain AU - Mairesse, Jean TI - Series which are both max-plus and min-plus rational are unambiguous JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 1 EP - 14 VL - 40 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2005042/ DO - 10.1051/ita:2005042 LA - en ID - ITA_2006__40_1_1_0 ER -
%0 Journal Article %A Lombardy, Sylvain %A Mairesse, Jean %T Series which are both max-plus and min-plus rational are unambiguous %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 1-14 %V 40 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2005042/ %R 10.1051/ita:2005042 %G en %F 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, Tome 40 (2006) no. 1, pp. 1-14. doi : 10.1051/ita:2005042. http://archive.numdam.org/articles/10.1051/ita:2005042/
[1] Synchronization and Linearity. John Wiley & Sons, New York (1992). | MR | Zbl
, , and ,[2] Transductions and context-free languages. B.G. Teubner (1979). | MR | Zbl
,[3] Rational Series and their Languages. Springer-Verlag (1988). | MR | Zbl
and ,[4] A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theoret. Comput. Sci. 134 (1994) 27-50. | Zbl
and ,[5] Automata, languages and machines, volume A. Academic Press, New York (1974). | MR | Zbl
,[6] Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont. 44 (1999) 683-698. | Zbl
and ,[7] Decidability of the equivalence problem for finitely ambiguous finance automata. Int. J. Algebra Comput. 12 (2002) 445-461. | Zbl
, and ,[8] Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co. (1979). | MR | Zbl
and ,[9] Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoret. Comput. Sci. 327 (2004) 349-373. | Zbl
, , and ,[10] The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 4 (1994) 405-425. | Zbl
,[11] Some consequences of a Fatou property of the tropical semiring. J. Pure Appl. Algebra 93 (1994) 231-249. | Zbl
,[12] Finite-state transducers in language and speech processing. Comput. Linguist. 23 (1997) 269-311.
,[13] Théorie algébrique des systèmes à événements discrets. Ph.D. thesis, École des Mines, Paris (1988).
,[14] A construction on finite automata that has remained hidden. Theoret. Comput. Sci. 204 (1998) 205-231. | Zbl
,[15] Éléments de théorie des automates. Vuibert Informatique, Paris (2003).
,[16] Automata Theoretic Aspects of Formal Powers Series. Springer-Verlag, Berlin (1978). | MR | Zbl
and ,[17] Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976/77) 243-259. | Zbl
,[18] 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
,[19] 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
and ,[20] Finite-valued distance automata. Theoret. Comput. Sci. 134 (1994) 225-251. | Zbl
,Cité par Sources :