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 psas. We give for this class an equivalent subclass of timed shuffle expressions and investigate closure properties by showing that psas are closed under union, concatenation, star, shuffle and renaming, but not under intersection. We also show that psas are equivalent with adtas, which are asynchronous compositions of timed automata in which time may evolve independently.

A study on shuffle, stopwatches and independently evolving clocks

LANOTTE, RUGGERO
2012-01-01

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 psas. We give for this class an equivalent subclass of timed shuffle expressions and investigate closure properties by showing that psas are closed under union, concatenation, star, shuffle and renaming, but not under intersection. We also show that psas are equivalent with adtas, which are asynchronous compositions of timed automata in which time may evolve independently.
Dima, C.; Lanotte, Ruggero
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/1789321
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact