Portal de Periódicos da CAPES

Undecidable Problems About Timed Automata

2006; Springer Science+Business Media; Linguagem: Inglês

10.1007/11867340_14

1611-3349

Olivier Finkel,

Logic, programming, and type systems

We solve some decision problems for timed automata which were raised by S. Tripakis in [Tri04] and by E. Asarin in [Asa04]. In particular, we show that one cannot decide whether a given timed automaton is determinizable or whether the complement of a timed regular language is timed regular. We show that the problem of the minimization of the number of clocks of a timed automaton is undecidable. It is also undecidable whether the shuffle of two timed regular languages is timed regular. We show that in the case of timed Büchi automata accepting infinite timed words some of these problems are Π1 1-hard, hence highly undecidable (located beyond the arithmetical hierarchy).