Document Open Access Logo

Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata

Author Erik Paul

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.137.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Erik Paul
  • Institute of Computer Science, Leipzig University, Germany

Funding

This work was partially supported by Deutsche Forschungsgemeinschaft (DFG), Graduiertenkolleg 1763 (QuantLA).

Cite AsGet BibTex

Erik Paul. Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 137:1-137:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.137

Abstract

We show that the finite sequentiality problem is decidable for finitely ambiguous max-plus tree automata. A max-plus tree automaton is a weighted tree automaton over the max-plus semiring. A max-plus tree automaton is called finitely ambiguous if the number of accepting runs on every tree is bounded by a global constant. The finite sequentiality problem asks whether for a given max-plus tree automaton, there exist finitely many deterministic max-plus tree automata whose pointwise maximum is equivalent to the given automaton.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantitative automata
  • Theory of computation → Tree languages
Keywords
  • Weighted Tree Automata
  • Max-Plus Tree Automata
  • Finite Sequentiality
  • Decidability
  • Finite Ambiguity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Athanasios Alexandrakis and Symeon Bozapalidis. Weighted grammars and Kleene’s theorem. Information Processing Letters, 24(1):1-4, 1987. Google Scholar
  2. Cyril Allauzen and Mehryar Mohri. Efficient algorithms for testing the twins property. Journal of Automata, Languages and Combinatorics, 8(2):117-144, 2003. Google Scholar
  3. Sebastian Bala. Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract). In Krishnendu Chatterjee and Jirí Sgall, editors, 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 8087 of Lecture Notes in Computer Science, pages 86-97. Springer, 2013. Google Scholar
  4. Sebastian Bala and Artur Koniński. Unambiguous automata denoting finitely sequential functions. In Adrian-Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, editors, 7th International Conference on Language and Automata Theory and Applications (LATA), volume 7810 of Lecture Notes in Computer Science, pages 104-115. Springer, 2013. Google Scholar
  5. Jean Berstel and Christophe Reutenauer. Recognizable formal power series on trees. Theoretical Computer Science, 18:115-148, 1982. Google Scholar
  6. Jean Berstel and Christophe Reutenauer. Rational Series and Their Languages, volume 12 of EATCS Monographs in Theoretical Computer Science. Springer, 1988. Google Scholar
  7. Johanna Björklund, Frank Drewes, and Niklas Zechner. An efficient best-trees algorithm for weighted tree automata over the tropical semiring. In Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, editors, 9th International Conference on Language and Automata Theory and Applications (LATA), volume 8977 of Lecture Notes in Computer Science, pages 97-108. Springer, 2015. Google Scholar
  8. Meera Blattner and Tom Head. Automata that recognize intersections of free submonoids. Information and Control, 35(3):173-176, 1977. Google Scholar
  9. Alexander Bockmayr, Volker Weispfenning, and Michael Maher. Solving numerical constraints. In Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning, volume 1, chapter 12, pages 751-842. Elsevier and MIT Press, 2001. Google Scholar
  10. Björn Borchardt. A pumping lemma and decidability problems for recognizable tree series. Acta Cybernetica, 16(4):509-544, 2004. Google Scholar
  11. Matthias Büchse, Jonathan May, and Heiko Vogler. Determinization of weighted tree automata using factorizations. Journal of Automata, Languages and Combinatorics, 15(3/4):229-254, 2010. Google Scholar
  12. Laure Daviaud, Pierre Guillon, and Glenn Merlet. Comparison of max-plus automata and joint spectral radius of tropical matrices. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  13. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, 2009. Google Scholar
  14. Zoltán Ésik and Werner Kuich. Formal tree series. Journal of Automata, Languages and Combinatorics, 8(2):219-285, 2003. Google Scholar
  15. Javier Esparza, Pierre Ganty, Stefan Kiefer, and Michael Luttenberger. Parikh’s theorem: A simple and direct automaton construction. Information Processing Letters, 111(12):614-619, 2011. Google Scholar
  16. Emmanuel Filiot, Ismaël Jecker, Nathan Lhote, Guillermo A. Pérez, and Jean-François Raskin. On delay and regret determinization of max-plus automata. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12. IEEE Computer Society, 2017. Google Scholar
  17. Zoltán Fülöp and Heiko Vogler. Weighted tree automata and tree transducers. In Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, chapter 9, pages 313-403. Springer, 2009. Google Scholar
  18. Kōsaburō Hashiguchi. Algorithms for determining relative star height and star height. Information and Computation, 78(2):124-169, 1988. Google Scholar
  19. Kōsaburō Hashiguchi, Kenichi Ishiguro, and Shūji Jimbo. Decidability of the equivalence problem for finitely ambiguous finance automata. International Journal of Algebra and Computation, 12(3):445-461, 2002. Google Scholar
  20. Daniel Kirsten. A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata. Informatique Théorique et Applications, 42(3):553-581, 2008. Google Scholar
  21. Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In Susanne Albers and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 3 of Leibniz International Proceedings in Informatics (LIPIcs), pages 589-600. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. Google Scholar
  22. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science, 327(3):349-373, 2004. Google Scholar
  23. Jan Komenda, Sébastien Lahaye, Jean-Louis Boimond, and Ton van den Boom. Max-plus algebra in the history of discrete event systems. Annual Reviews in Control, 45:240-249, 2018. Google Scholar
  24. Adam Koprowski and Johannes Waldmann. Max/plus tree automata for termination of term rewriting. Acta Cybernetica, 19(2):357-392, 2009. Google Scholar
  25. Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 113-122. IEEE Computer Society, 2013. Google Scholar
  26. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation, 4(3):405-426, 1994. Google Scholar
  27. Werner Kuich and Arto Salomaa. Semirings, Automata, Languages, volume 5 of EATCS Monographs in Theoretical Computer Science. Springer, 1986. Google Scholar
  28. Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science (STACS), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1-50:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  29. Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269-311, 1997. Google Scholar
  30. George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, 1988. Google Scholar
  31. Rohit Jivanlal Parikh. On context-free languages. Journal of the ACM, 13(4):570-581, 1966. Google Scholar
  32. Erik Paul. On finite and polynomial ambiguity of weighted tree automata. In Srečko Brlek and Christophe Reutenauer, editors, 20th International Conference on Developments in Language Theory (DLT), volume 9840 of Lecture Notes in Computer Science, pages 368-379. Springer, 2016. Google Scholar
  33. Erik Paul. The equivalence, unambiguity and sequentiality problems of finitely ambiguous max-plus tree automata are decidable. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1-53:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  34. Erik Paul. Finite sequentiality of unambiguous max-plus tree automata. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1-55:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  35. Slav Petrov. Latent variable grammars for natural language parsing. In Coarse-to-Fine Natural Language Processing, Theory and Applications of Natural Language Processing, chapter 2, pages 7-46. Springer, 2012. Google Scholar
  36. Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114-125, 1959. Google Scholar
  37. Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, series 2, 30:264-286, 1930. Google Scholar
  38. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  39. Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, 1978. Google Scholar
  40. Marcel-Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245-270, 1961. Google Scholar
  41. Helmut Seidl. On the finite degree of ambiguity of finite tree automata. Acta Informatica, 26(6):527-542, 1989. Google Scholar
  42. Imre Simon. Limited subsets of a free monoid. In 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 143-150. IEEE Computer Society, 1978. Google Scholar
  43. Imre Simon. Recognizable sets with multiplicities in the tropical semiring. In Michal P. Chytil, Ladislav Janiga, and Václav Koubek, editors, 13th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 324 of Lecture Notes in Computer Science, pages 107-120. Springer, 1988. Google Scholar
  44. Johannes Waldmann. Weighted automata for proving termination of string rewriting. Journal of Automata, Languages and Combinatorics, 12(4):545-570, 2007. Google Scholar
  45. Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact