[BBc13] Reducing interleaving semantics redundancy in reachability analysis of time Petri netsRevue Internationale avec comité de lecture : Journal ACM Transactions in Embedded Computing Systems (TECS) , vol. 12(1), pp. 1-24, 2013
Mots clés: Enumerative analysis, time Petri nets, state space explosion, interleaving semantics, reachability analysis
Résumé: The main problem of verification techniques based on exploration of (reachable) state space is the state explosion problem. In timed models, abstract states reached by different interleavings of the same set of transitions are, in general, different and their union is not necessarily an abstract state. To attenuate this state explosion, it would be interesting to reduce the redundancy caused by the interleaving semantics by agglomerating all these abstract states whenever their union is an abstract state. This article considers the time Petri net model and establishes some sufficient conditions that ensure that this union is an abstract state. In addition, it proposes a procedure to compute this union without computing beforehand intermediate abstract states. Finally, it shows how to use this result to improve the reachability analysis.