1 Distributed Systems and Semantics, The Faculty of Engineering and Science (ENG), Aalborg University, VBN2 Department of Computer Science, The Faculty of Engineering and Science (ENG), Aalborg University, VBN3 The Faculty of Engineering and Science (TECH), Aalborg University, VBN
Timed-arc Petri nets (TAPN) are a well-known time extension of thePetri net model and several translations to networks of timedautomata have been proposed for this model.We present a direct, DBM-basedalgorithm for forward reachability analysis of bounded TAPNs extended with transport arcs, inhibitor arcs and age invariants.We also give a complete proof of its correctness,including reduction techniques based on symmetries and extrapolation.Finally, we augment the algorithm with a novel state-spacereduction technique introducing a monotonic ordering on markings and prove its soundness even in the presence of monotonicity-breaking features like age invariants and inhibitor arcs. We implement the algorithm within the model-checkerTAPAAL and the experimental results document an encouraging performance compared to verification approaches that translate TAPN models to UPPAAL timed automata.
Electronic Proceedings in Theoretical Computer Science, 2012, Vol 102, p. 125-140
timed-arc Petri nets; verification; reachability; model checking
Main Research Area:
7th International Conference on Systems Software Verification, 2012