Project information
Decidability and complexity of observational equivalences on infinite - state processes
- Project Identification
- GA201/99/D026
- Project Period
- 9/1999 - 8/2002
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
-
Faculty of Informatics
- Mgr. Jitka Stříbrná, Ph.D.
- prof. RNDr. Mojmír Křetínský, CSc.
- Project Website
- http://www.fi.muni.cz/usr/stribrna/js-D026.html
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.
Publications
Total number of publications: 4
2002
-
Modifications of Expansion Trees for Weak Bisimulation in BPA
Verification of Infinite-State Systems Infinity'2002, year: 2002
2000
-
Some Remarks on Weak Bisimilarity of BPA-Processes
Year: 2000, number of pages: 26 s.
1999
-
Approximating Weak Bisimulation on Basic Process Algebras
Mathematical Foundations of Computer Science 1999, Proceedings, year: 1999
-
Approximating Weak Bisimulation on Basic Process Algebras
Year: 1999, number of pages: 18 s.