Reference:

P. Jančar, J. Esparza, and F. Moller. Petri nets and regular behaviours. Journal of Computer and System Sciences, 59(3):476–503, 1999.

Abstract:

We consider the following problems: (a) Given a labelled Petri net and a finite automaton, are they equivalent? (b) Given a labelled Petri net, is it equivalent to some (unspecified) finite automaton? These questions are studied within the framework of trace and bisimulation equivalences, in both their strong and weak versions. (In the weak version a special action—likened to an -move in automata theory—is considered to be non-observable.) We demonstrate that (a) is decidable for strong and weak trace equivalence and for strong bisimulation equivalence, but undecidable for weak bisimulation equivalence. On the other hand, we show that (b) is decidable for strong bisimulation equivalence, and undecidable for strong and weak trace equivalence, as well as for weak bisimulation equivalence.

Suggested BibTeX entry:

@article{JEM99,
    author = {P. Jan\v{c}ar and J. Esparza and F. Moller},
    journal = {Journal of Computer and System Sciences},
    number = {3},
    pages = {476--503},
    publisher = {Academic Press},
    title = {Petri Nets and Regular Behaviours},
    volume = {59},
    year = {1999}
}