Some techniques used to solve decidability and complexity questions for bisimulation-like equivalences

Petr Jancar

(University of Ostrava, Czech Republic)

A method of converting a computational problem to a two-player game and its use in showing P-hardness of behavioural equivalences for finite-state systems and their undecidability for Petri nets will be shown.

Then the "semilinear witness" method will be demonstrated in the case of a "regular" plane colouring technique which was used to show decidability of simulation and bisimulation equivalences for (weak) one-counter machines.
Tuesday 3rd April 2001, 14:00
Robert Recorde Room
Department of Computer Science