Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Duration-constrained regular expressions

Li Xuandong1, 2 Contact Information, Zhao Jianhua1, 2, Zheng Tao1, 2, Li Yong1, 2 and Zheng Guoliang1, 2

(1) State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, P.R. China
(2) Department of Computer Science and Technology, Nanjing University, Nanjing, Jiangsu, P.R. China, 210093

Published online: 28 April 2004

Abstract.  This paper investigates the logic-automata-connection for Duration Calculus. It has been frequently observed that Duration Calculus with linear duration terms comes close to being a logic of linear hybrid automata. We attempt to make this relation precise by constructing Kleene-connection between duration-constrained regular expressions and a subclass of linear hybrid automata called loop-reset automata in which any variable tested in a loop is reset in the same loop. The formalism of duration-constrained regular expressions is an extension of regular expressions with duration constraints, which are essentially formulas of Duration Calculus without negation, yet extended by a Kleene-star operator. In this paper, we show that this formalism is equivalent in expressive power to loop-reset automata by providing a translation procedure from expressions to automata and vice verse.

Keywords  Duration Calculus - Hybrid automata - Regular expressions

Received June 1999
Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones

Contact InformationLi Xuandong
Email: lxd@nju.edu.cn
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.114 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)