Document Open Access Logo

Finite Sequentiality of Unambiguous Max-Plus Tree Automata

Author Erik Paul

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.55.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

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

Funding

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

Cite As Get BibTex

Erik Paul. Finite Sequentiality of Unambiguous Max-Plus Tree Automata. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.55

Abstract

We show the decidability of the finite sequentiality problem for unambiguous max-plus tree automata. A max-plus tree automaton is called unambiguous if there is at most one accepting run on every tree. 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
  • Ambiguity

Metrics

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

References

  1. 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
  2. Sebastian Bala. Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions? In Krishnendu Chatterjee and Jiří 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
  3. 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
  4. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theoretical Computer Science, 292(1):45-63, 2003. Google Scholar
  5. Jean Berstel and Christophe Reutenauer. Rational Series and Their Languages. Springer, 1988. Google Scholar
  6. 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
  7. Meera Blattner and Tom Head. Automata That Recognize Intersections of Free Submonoids. Information and Control, 35(3):173-176, 1977. Google Scholar
  8. Matthias Büchse and Anja Fischer. Deciding the Twins Property for Weighted Tree Automata over Extremal Semifields. In Frank Drewes and Marco Kuhlmann, editors, Proceedings of the Workshop on Applications of Tree Automata Techniques in Natural Language Processing (ATANLP), pages 11-20. Association for Computational Linguistics, 2012. Google Scholar
  9. 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
  10. 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
  11. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, 2009. Google Scholar
  12. 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
  13. Kōsaburō Hashiguchi. Algorithms for Determining Relative Star Height and Star Height. Information and Computation, 78(2):124-169, 1988. Google Scholar
  14. 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
  15. 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
  16. Daniel Kirsten. Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring. Theoretical Computer Science, 420:56-63, 2012. Google Scholar
  17. 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
  18. 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
  19. 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
  20. Adam Koprowski and Johannes Waldmann. Max/Plus Tree Automata for Termination of Term Rewriting. Acta Cybernetica, 19(2):357-392, 2009. Google Scholar
  21. 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
  22. Werner Kuich and Arto Salomaa. Semirings, Automata, Languages. Springer, 1986. Google Scholar
  23. 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
  24. Mehryar Mohri. Finite-State Transducers in Language and Speech Processing. Computational Linguistics, 23(2):269-311, 1997. Google Scholar
  25. Mehryar Mohri. Weighted automata algorithms. In Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, chapter 6, pages 213-254. Springer, 2009. Google Scholar
  26. 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
  27. Slav Petrov. Latent Variable Grammars for Natural Language Parsing. In Coarse-to-Fine Natural Language Processing, chapter 2, pages 7-46. Springer, 2012. Google Scholar
  28. 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
  29. Jacques Sakarovitch. A Construction on Finite Automata that has Remained Hidden. Theoretical Computer Science, 204(1-2):205-231, 1998. Google Scholar
  30. Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer, 1978. Google Scholar
  31. Marcel-Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2–3):245-270, 1961. Google Scholar
  32. Marcel-Paul Schützenberger. Sur les Relations Rationnelles Entre Monoïdes Libres. Theoretical Computer Science, 3(2):243-259, 1976. Google Scholar
  33. Helmut Seidl. On the Finite Degree of Ambiguity of Finite Tree Automata. Acta Informatica, 26(6):527-542, 1989. Google Scholar
  34. 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
  35. Imre Simon. Recognizable Sets with Multiplicities in the Tropical Semiring. In Michal Chytil, Ladislav Janiga, and Václav Koubek, editors, Mathematical Foundations of Computer Science (MFCS), volume 324 of Lecture Notes in Computer Science, pages 107-120. Springer, 1988. Google Scholar
  36. Johannes Waldmann. Weighted Automata for Proving Termination of String Rewriting. Journal of Automata, Languages and Combinatorics, 12(4):545-570, 2007. Google Scholar
  37. 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 About DROPS Imprint Privacy Contact