Paper: A Kleene theorem for timed automata (at LICS 1997)

Authors: Eugene Asarin Paul Caspi Oded Maler

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 /spl omega/-regular expressions (Buchi's theorem).

BibTeX

  @InProceedings{AsarinCaspiMaler-AKleenetheoremforti,
    author = 	 {Eugene Asarin and Paul Caspi and Oded Maler},
    title = 	 {A Kleene theorem for timed automata},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS 1997)},
    year =	 {1997},
    month =	 {June}, 
    pages =      {160--171},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }