The Coarsest Congruence for Timed Automata with Deadlines Contained in Bisimulation


D'Argenio, P.R. and Gebremichael, B. (2005) The Coarsest Congruence for Timed Automata with Deadlines Contained in Bisimulation. In: Proceedings of CONCUR 2005, 23-26 Aug 2005, San Francisco, USA (pp. pp. 125-140).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:Delaying the synchronization of actions may reveal some hidden behavior that would not happen if the synchronization met the specified deadlines. This precise phenomenon makes bisimulation fail to be a congruence for the parallel composition of timed automata with deadlines, a variant of timed automata where time progress is controlled by deadlines imposed on each transition. This problem has been known and unsolved for several years. In this paper we give a characterization of the coarsest congruence that is included in the bisimulation relation. In addition, a symbolic characterization of such relation is provided and shown to be decidable. We also discuss the pitfalls of existing parallel compositions in this setting and argue that our definition is both reasonable and sufficiently expressive as to consider the modeling of both soft and hard real-time constraints.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 248128