Efficient contextual unfolding

César Rodríguez 1 Stefan Schwoon 1 Paolo Baldan
1 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : A contextual net is a Petri net extended with read arcs, which allow 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 earlier work; however, no concrete implementation existed. Here, we close this gap providing 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 the place-replication encoding of contextual nets into Petri nets.
Type de document :
Communication dans un congrès
Katoen, Joost-Pieter and König, Barbara. Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR'11), 2011, Aachen, Germany, Germany. Springer, 6901, pp.342-357, 2011, 〈10.1007/978-3-642-23217-6_23〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00779950
Contributeur : Stefan Haar <>
Soumis le : mardi 22 janvier 2013 - 17:37:01
Dernière modification le : jeudi 11 janvier 2018 - 06:23:37

Lien texte intégral

Identifiants

Collections

Citation

César Rodríguez, Stefan Schwoon, Paolo Baldan. Efficient contextual unfolding. Katoen, Joost-Pieter and König, Barbara. Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR'11), 2011, Aachen, Germany, Germany. Springer, 6901, pp.342-357, 2011, 〈10.1007/978-3-642-23217-6_23〉. 〈hal-00779950〉

Partager

Métriques

Consultations de la notice

172