Decidability Questions for Bisimilarity of Petri Nets and Some Related Problems

Petr Jancar

Abstract: The main result is undecidability of bisimilarity for labelled (place/transition) Petri nets. The same technique applies to the (prefix) language equivalence and reachability set equality, which yields stronger versions with simpler proofs of already known results. The paper also shows decidability of bisimilarity if one of the nets is deterministic up to bisimilarity. Another decidability result concerns semilinear bisimulations and extends the result for Basic Parallel Processes (BPP).

LFCS report ECS-LFCS-93-261, April 1993.

Previous | Index | Next