Document Open Access Logo

The Containment Problem for Unambiguous Register Automata

Authors Antoine Mottet , Karin Quaas

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.53.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Antoine Mottet
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Czech Republic
Karin Quaas
  • University of Oldenburg, Germany

Funding

  • Mottet, Antoine: This author received funding from DFG Graduiertenkolleg 1763 (QuantLA) and from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 771005, "CoCoSym").
  • Quaas, Karin: Supported by DFG, QU 316/1-2.

Cite AsGet BibTex

Antoine Mottet and Karin Quaas. The Containment Problem for Unambiguous Register Automata. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.53

Abstract

We investigate the complexity of the containment problem "Does L(A)subseteq L(B) hold?", where B is an unambiguous register automaton and A is an arbitrary register automaton. We prove that the problem is decidable and give upper bounds on the computational complexity in the general case, and when B is restricted to have a fixed number of registers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • Data words
  • Register automata
  • Unambiguous Automata
  • Containment Problem
  • Language Inclusion Problem

Metrics

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

References

  1. Thomas Colcombet. Forms of Determinism for Automata (Invited Talk). In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 1-23. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2012.1.
  2. Thomas Colcombet. Unambiguity in Automata Theory. In Jeffrey Shallit and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, volume 9118 of Lecture Notes in Computer Science, pages 3-18. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19225-3_1.
  3. Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. Pérez, and James Worrell. When is Containment Decidable for Probabilistic Automata? In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 121:1-121:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.121.
  4. Stéphane Demri and Ranko Lazic. LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log., 10(3), 2009. URL: http://dx.doi.org/10.1145/1507244.1507246.
  5. Diego Figueira. Alternating register automata on finite words and trees. Logical Methods in Computer Science, 8(1), 2012. URL: http://dx.doi.org/10.2168/LMCS-8(1:22)2012.
  6. Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. Ackermannian and Primitive-Recursive Bounds with Dickson’s Lemma. In Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada, pages 269-278. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/LICS.2011.39.
  7. Diego Figueira, Piotr Hofman, and Slawomir Lasota. Relating timed and register automata. In Sibylle B. Fröschle and Frank D. Valencia, editors, Proceedings 17th International Workshop on Expressiveness in Concurrency, EXPRESS'10, Paris, France, August 30th, 2010., volume 41 of EPTCS, pages 61-75, 2010. URL: http://dx.doi.org/10.4204/EPTCS.41.5.
  8. Nathanaël Fijalkow, Cristian Riveros, and James Worrell. Probabilistic Automata of Bounded Ambiguity. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, volume 85 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2017.19.
  9. Wilfrid Hodges. A shorter model theory. Cambridge University Press, Cambridge, 1997. Google Scholar
  10. Michael Kaminski and Nissim Francez. Finite-Memory Automata. Theor. Comput. Sci., 134(2):329-363, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90242-9.
  11. Michael Kaminski and Daniel Zeitlin. Finite-memory automata with non-deterministic reassignment. International Journal of Foundations of Computer Science, Volume 21, Issue 05, 2010. Google Scholar
  12. Hing Leung. Descriptional complexity of nfa of different ambiguity. Int. J. Found. Comput. Sci., 16(5):975-984, 2005. URL: http://dx.doi.org/10.1142/S0129054105003418.
  13. Michał Skrzypczak. Unambiguous Languages Exhaust the Index Hierarchy. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 140:1-140:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.140.
  14. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403-435, 2004. URL: http://dx.doi.org/10.1145/1013560.1013562.
  15. Joël Ouaknine and James Worrell. On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap. In 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 14-17 July 2004, Turku, Finland, Proceedings, pages 54-63. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/LICS.2004.1319600.
  16. Mikhail Raskin. A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 138:1-138:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.138.
  17. Hiroshi Sakamoto and Daisuke Ikeda. Intractability of decision problems for finite-memory automata. Theor. Comput. Sci., 231(2):297-308, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00105-X.
  18. Luc Segoufin. Automata and Logics for Words and Trees over an Infinite Alphabet. In Zoltán Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 41-57. Springer, 2006. URL: http://dx.doi.org/10.1007/11874683_3.
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