Title :
A Kleene theorem for timed automata
Author :
Asarin, Eugene ; Caspi, Paul ; Maler, Oded
Author_Institution :
Inst. for Inf. Transmission Problems, Moscow, Russia
fDate :
29 Jun-2 Jul 1997
Abstract :
In this paper we define timed regular expressions, and extension of regular expressions for specifying sets of dense-time discrete-valued signals. We show that this formalism is equivalent in expressive power to the timed automata of Alur and Dill by providing a translation procedure from expressions to automata and vice versa. the result is extended to ω-regular expressions (Buchi´s theorem)
Keywords :
automata theory; ω-regular expressions; Kleene theorem; dense-time discrete-valued signals; expressive power; timed automata; timed regular expressions; Algebra; Automata; Clocks; Concurrent computing; Equations; Logic functions; Real time systems;
Conference_Titel :
Logic in Computer Science, 1997. LICS '97. Proceedings., 12th Annual IEEE Symposium on
Conference_Location :
Warsaw
Print_ISBN :
0-8186-7925-5
DOI :
10.1109/LICS.1997.614944