Computer Science – Logic in Computer Science
Scientific paper
2007-12-09
Dans Proceedings of the 4th International Conference on Formal Modelling and Analysis of Timed Systems - FORMATS'06, France (2
Computer Science
Logic in Computer Science
Scientific paper
We solve some decision problems for timed automata which were recently raised by S. Tripakis in [ Folk Theorems on the Determinization and Minimization of Timed Automata, in the Proceedings of the International Workshop FORMATS'2003, LNCS, Volume 2791, p. 182-188, 2004 ] and by E. Asarin in [ Challenges in Timed Languages, From Applied Theory to Basic Theory, Bulletin of the EATCS, Volume 83, p. 106-120, 2004 ]. 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\"uchi automata accepting infinite timed words some of these problems are Pi^1_1-hard, hence highly undecidable (located beyond the arithmetical hierarchy).
No associations
LandOfFree
Undecidable Problems About Timed Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Undecidable Problems About Timed Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undecidable Problems About Timed Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-404756