Efficient unfolding of contextual Petri nets

Abstract : A contextual net is a Petri net extended with read arcs, which allows transitions to check for tokens without consuming them. Contextual nets allow for better modelling of concurrent read access than Petri nets, and their unfoldings can be exponentially more compact than those of a corresponding Petri net. A constructive but abstract procedure for generating those unfoldings was proposed in previous work. However, it remained unclear whether the approach was useful in practice and which data structures and algorithms would be appropriate to implement it. Here, we address this question. We provide two concrete methods for computing contextual unfoldings, with a view to efficiency. We report on experiments carried out on a number of benchmarks. These show that not only are contextual unfoldings more compact than Petri net unfoldings, but they can be computed with the same or better efficiency, in particular with respect to alternative approaches based on encodings of contextual nets into Petri nets.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, 449 (1), pp.2-22. 〈10.1016/j.tcs.2012.04.046〉
Liste complète des métadonnées

Contributeur : Benedikt Bollig <>
Soumis le : mercredi 16 janvier 2013 - 10:29:26
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Lien texte intégral




Paolo Baldan, Alessandro Bruni, Andrea Corradini, Barbara König, César Rodríguez, et al.. Efficient unfolding of contextual Petri nets. Theoretical Computer Science, Elsevier, 2012, 449 (1), pp.2-22. 〈10.1016/j.tcs.2012.04.046〉. 〈hal-00776752〉



Consultations de la notice