Abstract
We prove that timed regular expressions without renaming are strictly less expressive than timed automata, as conjectured by Asarin, Caspi and Maler in [3], where this extension of regular expressions was introduced. We also show how this result allows us to exhibit an infinite hierarchy of timed regular expressions.
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
R. Alur and D.L. Dill: Automata for Modelling Real-Time Systems. Proceedings of ICALP’90, LNCS 443, pages 322–335, 1990. 49
R. Alur and D.L. Dill: A Theory of Timed Automata, Theoretical Computer Science 126, pages 183–235, 1994. 47
E. Asarin, P. Caspi and O. Maler: A Kleene Theorem for Timed Automata. Proceedings of LICS’97, pages 160–170, 1997. 47, 47, 47, 48, 50, 52, 53, 58
B. Bérard, V. Diekert, P. Gastin and A. Petit: Characterization of the Expressive Power of Silent Transitions in Timed Automata. Fundamenta Informaticœ 36, pages 145–182, 1998. 50
V. Diekert, P. Gastin and A. Petit: Removing ε-Transitions in Timed Automata. Proceedings of STACS’97, LNCS 1200, pages 583–594, 1997.
P. Herrmann: Timed Automata and Recognizability. Information Processing Letters 65, pages 313–318, 1998. 50, 51
S.C. Kleene, Representations of Events in Nerve Nets and Finite Automata. Automata Studies, pages 3–42, 1956. 47
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herrmann, P. (1999). Renaming Is Necessary in Timed Regular Expressions. In: Rangan, C.P., Raman, V., Ramanujam, R. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1999. Lecture Notes in Computer Science, vol 1738. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46691-6_4
Download citation
DOI: https://doi.org/10.1007/3-540-46691-6_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66836-7
Online ISBN: 978-3-540-46691-8
eBook Packages: Springer Book Archive