TCS / Research / Publications / Parallelisation of the Petri Net Unfolding Algorithm
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Parallelisation of the Petri Net Unfolding Algorithm

Reference:

Keijo Heljanko, Victor Khomenko, and Maciej Koutny. Parallelisation of the Petri net unfolding algorithm. In Joost-Pieter Katoen and Perdita Stevens, editors, Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'2002), volume 2280 of Lecture Notes in Computer Science, pages 371–385, Grenoble, France, April 2002. Springer-Verlag.

Abstract:

In this paper, we first present theoretical results, helping to understand the unfolding algorithm presented in [6,7]. We then propose a modification of this algorithm, which can be efficiently parallelised and admits a more efficient implementation. Our experiments demonstrate that the degree of parallelism is usually quite high and resulting algorithms potentially can achieve significant speedup comparing with the sequential case.

Keywords:

model checking, Petri nets, parallel algorithm, unfolding, causality, concurrency

Suggested BibTeX entry:

@inproceedings{HelKhoKou:TACAS2002,
    address = {Grenoble, France},
    author = {Keijo Heljanko and Victor Khomenko and Maciej Koutny},
    booktitle = {Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'2002)},
    editor = {Joost-Pieter Katoen and Perdita Stevens},
    month = {April},
    pages = {371--385},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Parallelisation of the {Petri} Net Unfolding Algorithm},
    volume = {2280},
    year = {2002},
}

See www.tcs.hut.fi ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.