Alternating Timed Automata

Details Alternating Timed Automata Alternating Timed Automata

2005-12-08

arxiv.org/abs/cs/0512031v2

Computer Science

Logic in Computer Science

the full version of the Fossacs'05 conference preliminary paper revised according ot the referee's comments

Scientific paper

A notion of alternating timed automata is proposed. It is shown that such automata with only one clock have decidable emptiness problem over finite words. This gives a new class of timed languages which is closed under boolean operations and which has an effective presentation. We prove that the complexity of the emptiness problem for alternating timed automata with one clock is non-primitive recursive. The proof gives also the same lower bound for the universality problem for nondeterministic timed automata with one clock. We investigate extension of the model with epsilon-transitions and prove that emptiness is undecidable. Over infinite words, we show undecidability of the universality problem.

Affiliated with

Also associated with

No associations

Rating

Alternating 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 Alternating Timed Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternating Timed Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-442938