Undecidability of Weak Bisimilarity for PA-Processes

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SRBA Jiří

Year of publication 2003
Type Article in Proceedings
Conference Proceedings of 6th International Conference on Developments in Language Theory (DLT'02),
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.brics.dk/~srba/publ.html
Field Informatics
Keywords weak bisimilarity; undecidability; PA-processes
Description We prove that the problem whether two PA-processes are weakly bisimilar is undecidable. We combine several proof techniques to provide a reduction from Post's correspondence problem to our problem: existential quantification technique, masking technique and deadlock elimination technique.
Related projects:

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