• People
• Events
• Research

High undecidability of weak bisimilarity for Petri nets

Abstract: It is shown that the problem whether two labelled place/transition Petri nets (with initial markings) are weakly bisimilar is highly undecidable -- it resides at least at level omega of the hyperarithmetical hierarchy. On the other hand it is in the first level of the analytical hierarchy; the question whether the problem is hyperarithmetical is left open here.

LFCS report ECS-LFCS-94-298, August 1994.