Undecidability of Weak Bisimilarity for PA-Processes

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

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
Citace
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ů