10.46298/lmcs-18(2:9)2022
https://lmcs.episciences.org/7345
Clemente, Lorenzo
Lorenzo
Clemente
Lasota, Sławomir
Sławomir
Lasota
Piórkowski, Radosław
Radosław
Piórkowski
European Commission
683080
A unified theory of finite-state recognisability
Determinisability of register and timed automata
The deterministic membership problem for timed automata asks whether the
timed language given by a nondeterministic timed automaton can be recognised by
a deterministic timed automaton. An analogous problem can be stated in the
setting of register automata. We draw the complete decidability/complexity
landscape of the deterministic membership problem, in the setting of both
register and timed automata. For register automata, we prove that the
deterministic membership problem is decidable when the input automaton is a
nondeterministic one-register automaton (possibly with epsilon transitions) and
the number of registers of the output deterministic register automaton is
fixed. This is optimal: We show that in all the other cases the problem is
undecidable, i.e., when either (1) the input nondeterministic automaton has two
registers or more (even without epsilon transitions), or (2) it uses guessing,
or (3) the number of registers of the output deterministic automaton is not
fixed. The landscape for timed automata follows a similar pattern. We show that
the problem is decidable when the input automaton is a one-clock
nondeterministic timed automaton without epsilon transitions and the number of
clocks of the output deterministic timed automaton is fixed. Again, this is
optimal: We show that the problem in all the other cases is undecidable, i.e.,
when either (1) the input nondeterministic timed automaton has two clocks or
more, or (2) it uses epsilon transitions, or (3) the number of clocks of the
output deterministic automaton is not fixed.
Comment: arXiv admin note: substantial text overlap with arXiv:2007.09340
episciences.org
Computer Science - Formal Languages and Automata Theory
Attribution 4.0 International (CC BY 4.0)
2021-12-15
2022-05-10
2022-05-10
eng
journal article
arXiv:2104.03690
10.48550/arXiv.2104.03690
1860-5974
https://lmcs.episciences.org/7345/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 18, Issue 2
Researchers
Students