A Kleene theorem for timed automata

22 November 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

Vol. 863 (10436871) , 160-171
https://doi.org/10.1109/lics.1997.614944

Abstract

In this paper we define timed regular expressions, and extension of regular expressions for specifying sets of dense-time discrete-valued signals. We show that this formalism is equivalent in expressive power to the timed automata of Alur and Dill by providing a translation procedure from expressions to automata and vice versa. the result is extended to /spl omega/-regular expressions (Buchi's theorem).

Keywords

AUTOMATA
CLOCKS
ALGEBRA
LOGIC FUNCTIONS
REAL TIME SYSTEMS
CONCURRENT COMPUTING
EQUATIONS

This publication has 3 references indexed in Scilit:

A theory of timed automata
Published by Elsevier ,2002
Regular Expressions and State Graphs for Automata
IEEE Transactions on Electronic Computers, 1960
Representation of Events in Nerve Nets and Finite Automata
Published by Walter de Gruyter GmbH ,1956