A study on shuffle, stopwatches and independently evolving clocks |
| |
Authors: | C?t?lin Dima Ruggero Lanotte |
| |
Affiliation: | 1. LACL, Universit?? Paris-Est Cr??teil, 61 av. du G??n??ral de Gaulle, 94010, Cr??teil Cedex, France 2. Universit?? dell??Insubria, Via Carloni 78, 22100, Como, Italy
|
| |
Abstract: | We show that stopwatch automata are equivalent with timed shuffle expressions, an extension of timed regular expressions with
the shuffle operation. Since the emptiness problem is undecidable for stopwatch automata, and hence also for timed shuffle
expressions, we introduce a decidable subclass of stopwatch automata called partitioned stopwatch automata. We give for this
class an equivalent subclass of timed shuffle expressions and investigate closure properties by showing that partitioned stopwatch
automata are closed under union, concatenation, star, shuffle and renaming, but not under intersection. We also show that
partitioned stopwatch automata are equivalent with distributed time-asynchronous automata, which are asynchronous compositions
of timed automata in which time may evolve independently. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|