Nie jesteś zalogowany | Zaloguj się

One-clock timed automata

Prelegent(ci)
Slawomir Lasota
Afiliacja
Uniwersytet Warszawski
Termin
30 listopada 2005 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

For timed automata with two clocks emptyness in decidable but universality and containment are not. We will show that all these problems are decidable for alternating timed automata, but with only one clock. The non-primitive-recursive complexity will be shown. On infinite words, universality (and containment) will be shown undecidable for one-clock Buechi automata. We will also discuss relationships with timed temporal logics, possible extensions of our results and open problems.