Top

Theory of Computing Systems

Published in:

15-09-2020

The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata

Authors: Antoine Mottet, Karin Quaas

Published in: Theory of Computing Systems | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We investigate the complexity of the containment problem “Does \(L(\mathcal {A})\subseteq L({\mathscr{B}})\) hold?” for register automata and timed automata, where \({\mathscr{B}}\) is assumed to be unambiguous and \(\mathcal {A}\) is arbitrary. We prove that the problem is decidable in the case of register automata over \((\mathbb N,=)\), in the case of register automata over \((\mathbb Q,<)\) when \({\mathscr{B}}\) has a single register, and in the case of timed automata when \({\mathscr{B}}\) has a single clock. We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that \({\mathscr{B}}\) has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.

previous article Space Lower Bounds for the Signal Detection Problem

next article Finite Sequentiality of Unambiguous Max-Plus Tree Automata

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

We note that this coincides with the notion of support for a finite configuration, in the terminology of set theory with atoms. Similarly, some notions that we define hereafter are classical in the “atom” terminology. We choose to ignore this terminology for the sake of clarity.

Note the structural similarity to the unambiguous register automaton in Fig. 1.

Alur, R., Dill, D L: A theory of timed automata. Theor. Comput. Sci. 126(2), 183–235 (1994). https://doi.org/10.1016/0304-3975(94)90010-8MathSciNetCrossRefMATH

Colcombet, T.: Forms of determinism for automata (invited talk). In: Dürr, C, Wilke, T (eds.) 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, Vol 14 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 1–23 (2012), https://doi.org/10.4230/LIPIcs.STACS.2012.1

Colcombet, T.: Unambiguity in automata theory. In: Shallit, J, Okhotin, A (eds.) Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, vol 9118 of Lecture Notes in Computer Science, pp 3–18. Springer, New York (2015), https://doi.org/10.1007/978-3-319-19225-3_1

Daviaud, L., Jurdzinski, M., Lazic, R., Mazowiecki, F., Pérez, G A, Worrell, J.: When is containment decidable for probabilistic automata?. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp 121:1–121:14 (2018), https://doi.org/10.4230/LIPIcs.ICALP.2018.121

Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log. 10(3) https://doi.org/10.1145/1507244.1507246 (2009)

Figueira, D.: Alternating register automata on finite words and trees. Log. Meth. Comput. Sci. 8 (1) https://doi.org/10.2168/LMCS-8(1:22)2012 (2012)

Figueira, D., Figueira, S., Schmitz, S., Schnoebelen, P.: 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, IEEE Computer Society, pp 269–278 (2011), https://doi.org/10.1109/LICS.2011.39

Figueira, D., Hofman, P., Lasota, S.: Relating timed and register automata. Math. Struct. Comput. Sci. 26(6), 993–1021 (2016). https://doi.org/10.1017/S0960129514000322MathSciNetCrossRefMATH

Fijalkow, N., Riveros, C., Worrell, J.: Probabilistic automata of bounded ambiguity. In: Meyer, R, Nestmann, U (eds.) 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, vol 85 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 19:1–19:14 (2017), https://doi.org/10.4230/LIPIcs.CONCUR.2017.19

10.

Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329–363 (1994). https://doi.org/10.1016/0304-3975(94)90242-9MathSciNetCrossRefMATH

11.

Kaminski, M., Zeitlin, D.: Finite-memory automata with non-deterministic reassignment. Int. J. Found. Comput. Sci. 21(05) (2010)

12.

Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16(5), 975–984 (2005). https://doi.org/10.1142/S0129054105003418MathSciNetCrossRefMATH

13.

Skrzypczak, M.: Unambiguous languages exhaust the index hierarchy. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp 140:1–140:14 (2018), https://doi.org/10.4230/LIPIcs.ICALP.2018.140

14.

Mottet, A., Quaas, K.: The containment problem for unambiguous register automata. In: Niedermeier, R, Paul, C (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, vol 126 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 53:1–53:15 (2019), https://doi.org/10.4230/LIPIcs.STACS.2019.53

15.

Mottet, A., Quaas, K.: On the containment problem for unambiguous single-register automata with guessing. CoRR, abs/1905.12445, arXiv:1905.12445 (2019)

16.

Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 5(3), 403–435 (2004). https://doi.org/10.1145/1013560.1013562MathSciNetCrossRefMATH

17.

Ouaknine, J., Worrell, J.: 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, IEEE Computer Society, pp 54–63 (2004), https://doi.org/10.1109/LICS.2004.1319600

18.

Raskin, M.: A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp 138:1–138:11 (2018), https://doi.org/10.4230/LIPIcs.ICALP.2018.138

19.

Sakamoto, H., Ikeda, D.: Intractability of decision problems for finite-memory automata. Theor. Comput. Sci. 231(2), 297–308 (2000). https://doi.org/10.1016/S0304-3975(99)00105-XMathSciNetCrossRefMATH

20.

Schmitz, S., Schnoebelen, P.: Multiply-recursive upper bounds with higman’s lemma. In: Aceto, L, Henzinger, M, Sgall, J (eds.) Automata, languages and programming - 38th international colloquium, ICALP 2011, zurich, switzerland, july 4-8, 2011, proceedings, part II, vol 6756 of Lecture Notes in Computer Science, pp 441–452. Springer, New York (2011), https://doi.org/10.1007/978-3-642-22012-8_35

21.

Segoufin, L.: Automata and logics for words and trees over an infinite alphabet. In: Ésik, Z (ed.) Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, vol 4207 of Lecture Notes in Computer Science, pp 41–57. Springer, New York (2006), https://doi.org/10.1007/11874683_3

Title: The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Authors: Antoine Mottet
Karin Quaas
Publication date: 15-09-2020
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 4/2021
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-020-09997-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2021

Space Lower Bounds for the Signal Detection Problem

Token Sliding on Split Graphs

First-Order Orbit Queries

Finite Sequentiality of Unambiguous Max-Plus Tree Automata

Preface of STACS 2019 Special Issue

Premium Partner