Abstract
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 [Dim02] in connection with the problem of representing timing constraints.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Asarin, P. Caspi, and O. Maler. A Kleene theorem for timed automata. In Proceedings of LICS’97, pages 160–171, 1997.
E. Asarin, P. Caspi, and O. Maler. Timed regular expressions. Journal of ACM, 49:172–206, 2002.
R. Alur and D. Dill. A theory of timed automata. Theoretical Computer Science, 126:183–235, 1994.
E. Asarin and C. Dima. Balanced timed regular expressions. In Proceedings of MTCS’02, 2002. extended version to be published in ENTCS vol. 68.
S.L. Bloom and Z. Ésik. Axiomatizing shuffle and concatenation in languages. Information and Computation, 139:62–91, 1997.
R. Bellmann. Dynamic Programming. Princeton University Press, 1957.
P. Bouyer and A. Petit. Decomposition and composition of timed automata. In Proceedings of ICALP’99, volume 1644 of LNCS, pages 210–219, 1999.
P. Bouyer and A. Petit. A Kleene/Büchi-like theorem for clock languages. Journal of Automata, Languages and Combinatorics, 2002. To appear.
J.H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, 1971.
C. Dima. Kleene theoremsfor event-clock automata. In Proceedings of FCT’99, volume 1684 of LNCS, pages 215–225, 1999.
C. Dima. An algebraic theory of real-time formal languages. PhD thesis, Université Joseph Fourier Grenoble, France, 2001.
C. Dima. Computing reachability relationsin timed automata. In Proceedings of LICS’02, pages177–186, 2002.
S. Eilenberg. Automata, Languages, and Machines, volume A. Academic Press, 1974.
D. Kozen. A completenessth eorem for Kleene algebrasan d the algebra of regular events. Information and Computation, 110:366–390, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dima, C. (2003). Regular Expressions with Timed Dominoes. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds) Discrete Mathematics and Theoretical Computer Science. DMTCS 2003. Lecture Notes in Computer Science, vol 2731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45066-1_11
Download citation
DOI: https://doi.org/10.1007/3-540-45066-1_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40505-4
Online ISBN: 978-3-540-45066-5
eBook Packages: Springer Book Archive