Options
The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Publikationstyp
Journal Article
Date Issued
2021-05
Sprache
English
Author(s)
Journal
Volume
65
Issue
4
Start Page
706
End Page
735
Citation
Theory of Computing Systems 65 (4): 706-735 (2021-05)
Publisher DOI
Scopus ID
We investigate the complexity of the containment problem “Does L(A) ⊆ L(B) hold?” for register automata and timed automata, where B is assumed to be unambiguous and A is arbitrary. We prove that the problem is decidable in the case of register automata over (ℕ, =) , in the case of register automata over (ℚ, <) when B has a single register, and in the case of timed automata when 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 B has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.
Subjects
Containment
Register automata
Timed automata
Unambiguous automata