Séminaire du LIM (LIF et LSIS)
Mardi 19 juin à 14h - CMI, Salle de séminaire
Petr Jancar
Techn. Univ. Ostrava, Czech Rep.
Some techniques for decidability and complexity questions for bisimulation-like equivalences
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 a `semilinear witness' method will be demonstrated on the case of a `regular' plane colouring technique which was used to show decidability of the simulation and bisimulation equivalences for (weak) one-counter machines.
Page web : http://www.cs.vsb.cz/~jan59/