Undecidability of Weak Bisimilarity for PA-Processes
| Authors | |
|---|---|
| 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 | |
| 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: |