Document Open Access Logo

The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable

Author Erik Paul

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.53.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Erik Paul

Cite As Get BibTex

Erik Paul. The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.53

Abstract

We show that the equivalence, unambiguity and sequentiality problems are decidable for finitely ambiguous max-plus tree automata.

Subject Classification

Keywords
  • Tree Automata
  • Max-Plus Automata
  • Equivalence
  • Unambiguity
  • Sequentiality
  • Decidability

Metrics

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

References

  1. Sebastian Bala and Artur Koniński. Unambiguous automata denoting finitely sequential functions. In Adrian-Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, editors, Proc. LATA, volume 7810 of LNCS, pages 104-115. Springer, 2013. Google Scholar
  2. Jean Berstel and Christophe Reutenauer. Rational Series and Their Languages. Springer, 1988. Google Scholar
  3. 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
  4. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 2009. Google Scholar
  5. Stéphane Gaubert. Performance evaluation of (max,+) automata. IEEE T. Automat. Contr., 40(12):2014-2025, 1995. Google Scholar
  6. Stéphane Gaubert and Jean Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. IEEE T. Automat. Contr., 44(4):683-697, 1999. Google Scholar
  7. Kosaburo Hashiguchi. Algorithms for determining relative star height and star height. Inf. Comput., 78(2):124-169, 1988. Google Scholar
  8. Kosaburo Hashiguchi and Kenichi Ishiguro. Decidability of the equivalence problem for finitely ambiguous finance automata. Sūri Kaiseki Kenkyūsho Kōkyūroku, 960:23-36, 1996. Google Scholar
  9. Kosaburo Hashiguchi, Kenichi Ishiguro, and Shuji Jimbo. Decidability of the equivalence problem for finitely ambiguous finance automata. IJAC, 12(3):445-461, 2002. Google Scholar
  10. Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In Susanne Albers and Jean-Yves Marion Marion, editors, Proc. STACS, volume 3 of LIPIcs, pages 589-600. LZI, 2009. Google Scholar
  11. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theor. Comput. Sci., 327(3):349-373, 2004. Google Scholar
  12. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. IJAC, 4(3):405-426, 1994. Google Scholar
  13. Werner Kuich and Arto Salomaa. Semirings, Automata, Languages. Springer, 1986. Google Scholar
  14. Mehryar Mohri. Finite-state transducers in language and speech processing. Comput. Linguist., 23(2):269-311, 1997. Google Scholar
  15. George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. John Wiley &Sons, 1988. Google Scholar
  16. Erik Paul. On finite and polynomial ambiguity of weighted tree automata. In Srečko Brlek and Christophe Reutenauer, editors, Proc. DLT, volume 9840 of LNCS, pages 368-379. Springer, 2016. Google Scholar
  17. 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
  18. Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer, 1978. Google Scholar
  19. Marcel-Paul Schützenberger. On the definition of a family of automata. Inform. Control, 4(2–3):245 - 270, 1961. Google Scholar
  20. Imre Simon. Limited subsets of a free monoid. In Proc. FOCS, pages 143-150. IEEE Computer Society, 1978. Google Scholar
  21. Imre Simon. Recognizable sets with multiplicities in the tropical semiring. In Michal Chytil, Ladislav Janiga, and Václav Koubek, editors, Proc. MFCS, volume 324 of LNCS, pages 107-120. Springer, 1988. Google Scholar
  22. Andreas Weber. Finite-valued distance automata. Theor. Comput. Sci., 134(1):225-251, 1994. 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