Options
The containment problem for unambiguous register automata
Publikationstyp
Conference Paper
Date Issued
2019-03
Sprache
English
Author(s)
First published in
Number in series
126
Article Number
53
Citation
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 126: 53 (2019)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
ISBN of container
978-3-95977-100-9
We investigate the complexity of the containment problem “Does L(A) ⊆ 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.
Subjects
Containment problem
Data words
Language inclusion problem
Register automata
Unambiguous automata