Artículos de revistas
Classes of timed automata and the undecidability of universality
Registro en:
Fundamenta Informaticae. Ios Press, v. 82, n. 41671, n. 171, n. 184, 2008.
0169-2968
WOS:000252980000012
Autor
Moura, AV
Pinto, GA
Institución
Resumen
Universality for deterministic Timed Buchi Automata (TBA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TBA is II11- hard and its precise position in the analytical hierarchy is still an open question. In this paper we introduce two types of syntactical restrictions to nondeterministic TBA, which are of independent interest, and show that their universality problem is II11-complete. These restrictions define, as we prove, proper subclasses of the class of timed languages defined by nondeterministic TBA. This suggests, as we argue, that no solution to that open question will come without surprise. We also establish closure properties and the relationships between the classes of languages we describe. 82 41671 171 184