Undecidability and incompleteness results in automata theory

In this work, we study decision problems related to timed automata with silent transitions (TA$_{ε}$) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent ...

In this work, we study decision problems related to timed automata with silent transitions (TA$_{ε}$) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent ...

Universality for deterministic Timed Büchi Automata (TBA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TBA is Π$^1_1$-hard and its precise position in ...