Tags:abstract local zone graph, abstraction operator, finite abstraction, local-time semantics, model checking, partial order reduction, partial-order methods, reachability, timed automata and timed network
Abstract:
A timed network is a parallel composition of timed automata synchronizing on common actions. We develop a methodology that allows to use partial-order methods for the reachability problem in timed networks. It is based on a local-time semantics [Bengtsson et al. (1998)]. A new simulation based abstraction of local-time zones is proposed. An efficient algorithm for testing subsumption with respect to this abstraction is developed. The abstraction is not finite in general. We show that, under some weak assumptions, there is no finite abstraction for local-time zones that works for arbitrary networks. We introduce a notion of bounded spread networks, where it is possible to use subsumption and partial-order methods at the same time.
Abstractions for the Local-Time Semantics of Timed Automata: a Foundation for Partial-Order Methods