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.*