Some techniques and results in deciding bisimilarity

Petr Jancar
Technical University of Ostrava
Friday, 16 December, 2005 (All day)

The planned aim of the talk is to highlight the author's main results and techniques dealing with decidability and complexity questions for bisimilarity. This includes the general result of undecidability of (behavioural) equivalences on (labelled place/transition) Petri nets, and PSPACE-completeness of bisimilarity on Basic Parallel Processes, using the technique of so called DD-functions. Also a fresh result (Jancar, Srba 2005) will be demonstrated, as a new application of so called Defender's choice technique; it shows the undecidability of bisimilarity on Type -1 systems (with prefix rewrite rules R --> w), by which an open question posed by Senizergues and Stirling is answered.