Undecidability of Weak Bisimilarity for PA-Processes

• Autoři: SRBA Jiří
• Rok publikování: 2003
• Druh: Článek ve sborníku
• Konference: Proceedings of 6th International Conference on Developments in Language Theory (DLT'02),
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://www.brics.dk/~srba/publ.html
• Obor: Informatika
• Klíčová slova: weak bisimilarity; undecidability; PA-processes
• Popis: 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.

Související projekty

• Verifikace nekonečně stavových systémů
• Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů