Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes

PD Dr. Richard Mayr
Albert-Ludwigs-University Freiburg

We show that checking weak bisimulation equivalence of 1-counter nets (Petri nets with only one unbounded place) is undecidable. This implies the undecidability of weak bisimulation equivalence for 1-counter machines. The undecidability result carries over to normed 1-counter nets/machines. This result implies that weak bisimulation equivalence is undecidable for most classes of infinite-state systems.

ASTEC seminar
March 8, 2004

Place: Information technology, Uppsala University
Room: 1113
Time: 13.15-14.00 (+ discussions)

Room 1113 is in building 1, floor 1, room 13 (in the southern part of the building).

Help on how to find ASTEC Seminars.

There will be an extended period for discussions after the seminar.

Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 14.00.

Everyone is welcome !

Updated 25-Feb-2004 10:36 by Roland Grönroos
e-mail: info -at-    Location: