Petri nets and the equivalence problem. (English) Zbl 0953.68571
Börger, Egon (ed.) et al., Computer science logic. 7th Workshop, CSL ’93, Swansea, GB, September 13-17, 1993. Selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 832, 165-174 (1994).
Summary: We prove that trace equivalence is undecidable for the very small and natural subclass of Petri nets in which no transition requires more than one token; this subclass corresponds exactly to the calculus BPP of Christensen for which bisimulation equivalence is known to be decidable. We present this result along with a survey of decidability results for various notions of equivalence with respect to various subclasses of Petri nets.
For the entire collection see [Zbl 0852.00043].
For the entire collection see [Zbl 0852.00043].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
