Document Open Access Logo

Pumping Lemmas for Weighted Automata

Authors Filip Mazowiecki, Cristian Riveros

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.50.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Filip Mazowiecki
Cristian Riveros

Cite As Get BibTex

Filip Mazowiecki and Cristian Riveros. Pumping Lemmas for Weighted Automata. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.50

Abstract

We present three pumping lemmas for three classes of functions definable by fragments of weighted automata over the min-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous, polynomially-ambiguous weighted automata, and the full class of weighted automata is strict for the min-plus semiring.

Subject Classification

Keywords
  • Weighted automata
  • regular functions over words
  • pumping lemmas

Metrics

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

References

  1. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? In Tevfik Bultan and Pao-Ann Hsiung, editors, Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011. Proceedings, volume 6996 of Lecture Notes in Computer Science, pages 482-491. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24372-1_37.
  2. Rajeev Alur, Loris D'Antoni, Jyotirmoy Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In LICS, pages 13-22. IEEE Computer Society, 2013. Google Scholar
  3. Rajeev Alur and Mukund Raghothaman. Decision problems for additive regular functions. In Automata, Languages, and Programming, pages 37-48. Springer, 2013. Google Scholar
  4. Marcelo Arenas, Martin Munoz, and Cristian Riveros. Descriptive complexity for counting complexity classes. In Logic in Computer Science (LICS), 2017 32nd Annual ACM/IEEE Symposium on, pages 1-12. IEEE, 2017. Google Scholar
  5. Udi Boker, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman. Temporal specifications with accumulative values. ACM Transactions on Computational Logic (TOCL), 15(4):27, 2014. Google Scholar
  6. Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Toruńczyk. Cost functions definable by min/max automata. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 29:1-29:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.29.
  7. Karel Culik II and Jarkko Kari. Image compression using weighted finite automata. In Mathematical Foundations of Computer Science 1993, pages 392-402. Springer, 1993. Google Scholar
  8. Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A generalised twinning property for minimisation of cost register automata. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 857-866. ACM, 2016. URL: http://dx.doi.org/10.1145/2933575.2934549.
  9. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theor. Comput. Sci., 380(1-2):69-86, 2007. Google Scholar
  10. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 1st edition, 2009. Google Scholar
  11. Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math, 49(129-141):13, 1961. Google Scholar
  12. Ronald Fraïsé. Sur quelques classification des systemes de relations. Université d$$1'Alger, Publications Scientifiques, Série A, 1:35-182, 1984. Google Scholar
  13. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  14. Daniel Kirsten. A burnside approach to the termination of mohri’s algorithm for polynomially ambiguous min-plus-automata. ITA, 42(3):553-581, 2008. URL: http://dx.doi.org/10.1051/ita:2008017.
  15. Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In STACS, pages 589-600, 2009. Google Scholar
  16. 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
  17. Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. In LICS, pages 113-122. IEEE Computer Society, 2013. Google Scholar
  18. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. In Werner Kuich, editor, Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings, volume 623 of Lecture Notes in Computer Science, pages 101-112. Springer, 1992. URL: http://dx.doi.org/10.1007/3-540-55719-9_67.
  19. Leonid Libkin. Elements of finite model theory. Springer Science &Business Media, 2013. Google Scholar
  20. Filip Mazowiecki and Cristian Riveros. Maximal partition logic: Towards a logical characterization of copyless cost register automata. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 144-159, 2015. Google Scholar
  21. Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 53:1-53:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.53.
  22. Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269-311, 1997. Google Scholar
  23. Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences,. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 318-329. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_27.
  24. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 330-341. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_28.
  25. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1993. Google Scholar
  26. Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7, 2010. Google Scholar
  27. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. URL: http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521844253.
  28. M. P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245-270, 1961. Google Scholar
  29. 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