Kleene theorems for event-clock automata

In this paper we define some class of regular expressions equivalent to event-clock automata. It is shown that regular expressions cannot be given a compositional semantics in terms of timed state sequences. We introduce a modified version of timed state sequences supporting a partial operation of concatenation on which we may build the semantics of regular expressions. A forgetting map then induces a semantics in terms of the classic version of timed state sequences. We also define several types of languages of automata in terms of classic or modified timed state sequences. Two Kleene theorems, one for each type of timed state sequences, relating expressions and event-clock automata are proved.

"Proceedings of 12th International Symposium on Funamentals of Computation Theory (FCT'99)", Iasi, Romania, 30 August - 2 September 1999, LNCS 1684, pages 214-224.

 gzipped postscript