Efficient unfolding of contextual Petri nets

P Baldan, A Bruni, A Corradini, B König… - Theoretical Computer …, 2012 - Elsevier
Theoretical Computer Science, 2012Elsevier
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 …
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果