I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Deciding finiteness of Petri nets up to bisimulation


P. Jancar and J. Esparza. Deciding finiteness of Petri nets up to bisimulation. In F. Meyer auf der Heide and B. Monien, editors, Proc. of ICALP'96, number 1099 in Lecture Notes in Computer Science, pages 478–489. Springer-Verlag, 1996.


We study the following problems for strong and weak bisimulation equivalence: Given a labelled Petri net and a finite transition system, are they equivalent? Given a labelled Petri net, is it equivalent to some (unspecified) finite transition system? We show that both problems are decidable for strong bisimulation and undecidable for weak bisimulation.

Suggested BibTeX entry:

    author = {P. Jancar and J. Esparza},
    booktitle = {Proc. of ICALP'96},
    editor = {F. Meyer auf der Heide and B. Monien},
    number = {1099},
    pages = {478--489},
    publisher = {{Springer-Verlag}},
    series = {{Lecture Notes in Computer Science}},
    title = {Deciding finiteness of {P}etri nets up to bisimulation},
    year = {1996}

GZipped PostScript (356 kB)
PDF (826 kB)
Tech report version