Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Decidability and Complexity of Petri Net Problems – an Introduction

Reference:

J. Esparza. Decidability and complexity of Petri net problems – an introduction. In G. Rozenberg and W. Reisig, editors, Lectures on Petri Nets I: Basic Models. Advances in Petri Nets, number 1491 in Lecture Notes in Computer Science, pages 374–428, 1998. Section 8 presents a logic for Petri nets, due to Yen, having an EXPSPACE model-checking problem. Unfortunately, Yen's paper has a mistake. For a description of the mistake and a partial correction see "On Yen's Path Logic for Petri Nets" by Faouzi and Habermehl, Workshop on Reachability Problems 2009.

Suggested BibTeX entry:

@inproceedings{Esp98a,
    author = {J. Esparza},
    booktitle = {Lectures on {P}etri Nets I: Basic Models. Advances in Petri Nets},
    editor = {G.~Rozenberg and W.~Reisig},
    note = {Section 8 presents a logic for Petri nets, due to Yen, having an EXPSPACE model-checking problem. Unfortunately, Yen's paper has a mistake. For a description of the mistake and a partial correction see "On Yen's Path Logic for Petri Nets" by Faouzi and Habermehl, Workshop on Reachability Problems 2009.},
    number = {1491},
    pages = {374--428},
    series = {Lecture Notes in Computer Science},
    title = {Decidability and Complexity of {P}etri Net Problems -- an Introduction},
    year = {1998}
}

GZipped PostScript (159 kB)
PDF (361 kB)