A New Approach to Abstract Reachability State Space of Time Petri Nets

Time Petri nets (TPN model) allow the specification of real-time systems involving explicit timing constraints. The main challenge of the analysis of such systems is to construct, with few resources (time and space), a coarse abstraction preserving timed properties. In this paper, we propose a new finite graph, called Timed Aggregate Graph (TAG), abstracting the behaviour of bounded TPNs with strong time semantics. The main feature of this abstract representation compared to existing approaches is the encoding of the time information. This is done in a pure way within each node of the TAG allowing to compute the minimum and maximum elapsed time in every path of the graph. The TAG preserves runs and reachable states of the corresponding TPN and allows for verification of both event- and state-based properties.