Petri nets and regular processes

We consider the following problems: (a) Given a labelled Petri net and a fi nite automaton, are they equivalent?; (b) Given a labelled Petri net, is it equivalent to some (unspecified) finite automaton? These questions are stu died within the framework of trace and bisimulation equivalences, in both t heir strong and weak versions. (In the weak version a special tau action-li kened to an epsilon-move in automata theory-is considered to be nonobservab le.) We demonstrate that (a) is decidable for strong and weak trace equival ence and for strong bisimulation equivalence, but undecidable for weak bisi mulation 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, (C) 1999 Academi c Press.