###### Options

# The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata

Publikationstyp

Journal Article

Publikationsdatum

2021-05

Sprache

English

Author

Enthalten in

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.