A Kleene Theorem for Piecewise Constant Signals Automata (extended abstract)

Jérôme Durand-Lose (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In this paper, we consider timed automata for piecewise constant signals.In the model presented here, time elapses only during transitions; any constraint on clocks should be satisfied during all the duration of the transition. Signal automata are very different from un-timed and time-event automata because piecewise constant signals may be split (and spliced) in an infinite number of ways. We show that there exist signal regular expressions with renaming describing exactly the languages accepted by signal automata. The constructions show the similarities and differences from the time-event model.

Dans ce rapport, nous considérons les automates temporiss sur des signaux constants par morceaux. Dans le modèle présent, le temps s’écoule durant les transitions; toute contrainte sur un transition devant être vérifié durant toute la transition. Les automates signaux sont très diffèrents de leurs homologues non temporiss ou vnement-date car les morceaux constants peuvent très découpés ou recollés d’une infinité de manières. Nous montrons qu’il existe des expressions rationnelles de signaux couplés des renommages qui décrivent exactement les mêmes langages que ceux acceptés par les automates signaux. Les constructions montrent les similarités et les diffèrences avec le modèle vnement-date

Mots clés: Piecewise Constant Signals; Regular Expression; Timed Automata

Mots clés: Automates temporiss; signaux constants par morceaux; expressions rationnelles

Domaines: Informatique [cs]

Jérôme Durand-Lose. A Kleene Theorem for Piecewise Constant Signals Automata (extended abstract). [Research Report] LIp RR-2002-43, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02102067⟩