Pasupuleti, Vijay S. and Pandya, Paritosh K. (2009) Determinization and expressiveness of integer reset timed automata with silent transitions. In: Third International Conference, LATA 2009, Tarragona, Spain, 2-8 Apr 2009. Published in: Language and Automata Theory and Applications, 5457 pp. 728-739. doi:10.1007/978-3-642-00982-2_62 ISSN 0302-9743.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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(A)⊆L(B was shown to be decidable when A is an ε-TA and 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 δ ✓-languages. Equivalence of deterministic and nondeterministic automata also gives us that these automata are closed under the boolean operations.

Item Type:	Conference Item (Paper)
Divisions:	Faculty of Science, Engineering and Medicine > Engineering > WMG (Formerly the Warwick Manufacturing Group)
Journal or Publication Title:	Language and Automata Theory and Applications
Publisher:	Springer Berlin Heidelberg
ISSN:	0302-9743
Book Title:	Language and Automata Theory and Applications
Official Date:	2009
Dates:	Date Event 2009 Modified
Volume:	5457
Page Range:	pp. 728-739
DOI:	10.1007/978-3-642-00982-2_62
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	Third International Conference, LATA 2009
Type of Event:	Conference
Location of Event:	Tarragona, Spain
Date(s) of Event:	2-8 Apr 2009

Request changes or add full text files to a record

Repository staff actions (login required)

View Item