Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Determinization and Expressiveness of Integer Reset Timed Automata with Silent Transitions

P. Vijay Suman19 and Paritosh K. Pandya19

(19)  Tata Institute of Fundamental Research, India
Abstract
ε-IRTA are a subclass of timed automata with ε moves (ε-TA). They are useful for modelling global sparse time base used in time-triggered architecture and distributed business processes. In a previous paper [1], the language inclusion problem $L({\mathcal A}) \subseteq L(\mathcal B$ was shown to be decidable when $\mathcal A$ is an ε-TA and $\mathcal B$ is an ε-IRTA. In this paper, we address the determinization, complementation and ε-removal questions for ε-IRTA. We introduce a new variant of timed automata called GRTA. We show that for every ε-IRTA we can effectively construct a language equivalent 1-clock, deterministic GRTA with periodic time guards (but having no ε moves). The construction gives rise to at most a double exponential blowup in the number of locations. Finally, we show that every GRTA with periodic guards can be reduced to a language equivalent ε-IRTA with at most double the number of locations. Thus, ε-IRTA, periodic GRTA, and deterministic 1-clock periodic GRTA have the same expressive power and that they are all expressively complete with respect to the regular δ $\checkmark$-languages. Equivalence of deterministic and nondeterministic automata also gives us that these automata are closed under the boolean operations.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)