Project information
Decidability and complexity of observational equivalences on infinite - state processes

Investor logo
Project Identification
Project Period
9/1999 - 8/2002
Investor / Pogramme / Project type
Czech Science Foundation
MU Faculty or unit
Faculty of Informatics
Project Website

The aim of the project is to contribute new knowledge to the study of concurrent systems, inparticular with regard to the decidability of the problems connected to verification of infinite - state processes. The main question we want to address is the te sting of certain observational equivalences on potentially infinite - state processes. In particular we want to study strong, and weak bisimulation equivalences on various process algebras, mainly BPA and BPPA, and their extensions PDA and PDDA, fro m the point of view of decidability and computational optimality of decision procedures that might exist. For strong bisimulation equivalence we want to find out whether there exist feasible (polynomial) decision algorithms for the aforementioned pr ocess algebras. In the case of weak bisimulation equivalence we want to investigate whether it is decidable on these classes of processes.


Total number of publications: 4

You are running an old browser version. We recommend updating your browser to its latest version.

More info