Duration-constrained regular expressions |
| |
Authors: | Email author" target="_blank">Li?XuandongEmail author Zhao?Jianhua Zheng?Tao Li?Yong Zheng?Guoliang |
| |
Affiliation: | (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 |
| |
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.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones |
| |
Keywords: | Duration Calculus Hybrid automata Regular expressions |
本文献已被 SpringerLink 等数据库收录! |
|