Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T18:27:32.882Z Has data issue: false hasContentIssue false
  • English
  • Français

Series which are both max-plus and min-plus rational are unambiguous

Published online by Cambridge University Press:  15 October 2005

Sylvain Lombardy  and
Jean Mairesse
Sylvain Lombardy
Affiliation:
LIAFA (UMR 7089), CNRS–Université Paris 7, 2 pl. Jussieu, 75251 Paris Cedex 05, France; [email protected], [email protected]
Jean Mairesse
Affiliation:
LIAFA (UMR 7089), CNRS–Université Paris 7, 2 pl. Jussieu, 75251 Paris Cedex 05, France; [email protected], [email protected]
Get access

Abstract

Consider partial maps ∑* → $\mathbb R$ 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.

Keywords

Rational seriesautomataunambiguousmax-plus semiringtropical semiring.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 1 , January 2006 , pp. 1 - 14
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronization and Linearity. John Wiley & Sons, New York (1992).
J. Berstel, Transductions and context-free languages. B.G. Teubner (1979).
J. Berstel and C. Reutenauer, Rational Series and their Languages. Springer-Verlag (1988).
Bonnier-Rigny, A. and Krob, D., A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theoret. Comput. Sci. 134 (1994) 27–50. CrossRef
S. Eilenberg, Automata, languages and machines, volume A. Academic Press, New York (1974).
Gaubert, S. and Mairesse, J., Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont. 44 (1999) 683–698. CrossRef
Hashigushi, K., Ishiguro, K. and Jimbo, S., Decidability of the equivalence problem for finitely ambiguous finance automata. Int. J. Algebra Comput. 12 (2002) 445–461. CrossRef
J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co. (1979).
Klimann, I., Lombardy, S., Mairesse, J. and Prieur, C., Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoret. Comput. Sci. 327 (2004) 349–373. CrossRef
Krob, D., The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 4 (1994) 405–425. CrossRef
Krob, D., Some consequences of a Fatou property of the tropical semiring. J. Pure Appl. Algebra 93 (1994) 231–249. CrossRef
Mohri, M., Finite-state transducers in language and speech processing. Comput. Linguist. 23 (1997) 269–311.
P. Moller, Théorie algébrique des systèmes à événements discrets. Ph.D. thesis, École des Mines, Paris (1988).
Sakarovitch, J., A construction on finite automata that has remained hidden. Theoret. Comput. Sci. 204 (1998) 205–231. CrossRef
J. Sakarovitch, Éléments de théorie des automates. Vuibert Informatique, Paris (2003).
A. Salomaa and M. Soittola, Automata Theoretic Aspects of Formal Powers Series. Springer-Verlag, Berlin (1978).
M.-P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976/77) 243–259.
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.
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.
Weber, A., Finite-valued distance automata. Theoret. Comput. Sci. 134 (1994) 225–251. CrossRef