Deciding the Sequentiality of a Finitely Ambiguous Max-Plus Automaton

  • Ines Klimann
  • Sylvain Lombardy
  • Jean Mairesse
  • Christophe Prieur
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable in an effective way whether a series that is recognized by a finitely ambiguous max-plus automaton is sequential. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    C. Allauzen and M. Mohri. Efficient algorithms for testing the twins property. Journal of Automata, Languages and Combinatorics, 2003. (To appear).Google Scholar
  2. 2.
    M.-P. Béal, O. Carton, C. Prieur, and J. Sakarovitch. Squaring transducers: An efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci., 292:45–63, 2003.zbMATHCrossRefGoogle Scholar
  3. 3.
    J. Berstel. Transductions and context-free languages. B. G. Teubner, 1979.Google Scholar
  4. 4.
    J. Berstel and C. Reutenauer. Rational Series and their Languages. Springer Verlag, 1988.Google Scholar
  5. 5.
    M. Brilman and J.M. Vincent. Dynamics of synchronized parallel systems. Stochastic Models, 13(3):605–619, 1997.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    A.L. Buchsbaum, R. Giancarlo, and J.R. Westbrook. On the determinization of weighted finite automata. SIAM J. Comput., 30(5):1502–1531, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    C. Choffrut. Une caractérisation des fonctions séquentielles et des fonctions sousséquentielles en tant que relations rationnelles. Theor. Comput. Sci., 5:325–337, 1977.CrossRefMathSciNetGoogle Scholar
  8. 8.
    C. Choffrut. Contribution à l’étude de quelques familles remarquables de fonctions rationnelles. Thèse d’état, Univ. Paris VII, 1978.Google Scholar
  9. 9.
    S. Eilenberg. Automata, languages and machines, vol. A. Academic Press, 1974.Google Scholar
  10. 10.
    S. Gaubert. Performance evaluation of (max,+) automata. IEEE Trans. Aut. Cont., 40(12):2014–2025, 1995.zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    S. Gaubert and J. Mairesse. Task resource models and (max,+) automata. In J. Gunawardena, editor, Idempotency, volume 11, pages 133–144. Cambridge University Press, 1998.Google Scholar
  12. 12.
    S. Gaubert and J. Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont., 44(4):683–698, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    K. Hashigushi. Algorithms for determining relative star height and star height. Inf. Comput., 78(2):124–169, 1988.CrossRefGoogle Scholar
  14. 14.
    K. Hashigushi, K. Ishiguro, and S. Jimbo. Decidability of the equivalence problem for finitely ambiguous finance automata. Int. J. Algebra Comput., 12(3):445–461, 2002.CrossRefGoogle Scholar
  15. 15.
    D. Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput., 4(3):405–425, 1994.zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    D. Krob and A. Bonnier-Rigny. A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theor. Comput. Sci., 134:27–50, 1994.zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    W. Kuich and A. Salomaa. Semirings, Automata, Languages, volume 5 of EATCS. Springer-Verlag, 1986.Google Scholar
  18. 18.
    M. Mohri. Finite-state transducers in language and speech processing. Comput. Linguist., 23(2):269–311, 1997.MathSciNetGoogle Scholar
  19. 19.
    P. Moller. Théorie algébrique des systémes à événements discrets. PhD thesis, École des Mines de Paris, 1988.Google Scholar
  20. 20.
    J. Sakarovitch. A construction in finite automata that has remained hidden. Theor. Comput. Sci., 204:205–231, 1998.zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    M.-P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2–3):245–270, 1961.zbMATHCrossRefMathSciNetGoogle Scholar
  22. 22.
    M.-P. Schützenberger. Sur les relations rationnelles entre monoïdes libres. Theor. Comput. Sci., 3:243–259, 1976.CrossRefGoogle Scholar
  23. 23.
    I. Simon. Recognizable sets with multiplicities in the tropical semiring. In Mathematical Foundations of Computer Science, Proc. 13th Symp., number 324 in LNCS, pages 107–120, 1988.Google Scholar
  24. 24.
    G.X. Viennot. Heaps of pieces, I: Basic definitions and combinatorial lemmas. In Labelle and Leroux, editors, Combinatoire Énumérative, number 1234 in Lect. Notes in Math., pages 321–350. Springer, 1986.Google Scholar
  25. 25.
    A. Weber. Finite-valued distance automata. Theor. Comput. Sci., 134:225–251, 1994.zbMATHCrossRefGoogle Scholar
  26. 26.
    A. Weber and R. Klemm. Economy of description for single-valued transducers. Information and Computation, 118(2):327–340, 1995.zbMATHCrossRefMathSciNetGoogle Scholar
  27. 27.
    A. Weber and H. Seidl. On the degree of ambiguity of finite automata. Theor. Comput. Sci., 88(2):325–349, 1991.zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Ines Klimann
    • 1
  • Sylvain Lombardy
    • 1
  • Jean Mairesse
    • 1
  • Christophe Prieur
    • 1
  1. 1.LIAFA, CNRS (umr 7089)Université Paris 7Paris Cedex 5France

Personalised recommendations