Regular Expressions with Timed Dominoes

We give a class of timed regular expressions that involve the use of colored parentheses for specifying timing constraints. The expressions are given in a matricial format, and their semantics is based upon an ``overlapping concatenation'' of timed words. We then give a calculus for emptiness checking of a regular expression, that does not go through translating expressions into timed automata. To this end we use the class of $2n$-automata, studied in a parallel paper (LICS'02) in connection with the problem of representing timing constraints.

Proceedings of 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS'03)”, Springer Verlag, Lecture Notes in Computer Science, vol. 2731, pages 141-154, 2003.

 gzipped postscript file.