# 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