Undecidability of Weak Bisimilarity for PA-Processes

Jiri Srba

Undecidability of Weak Bisimilarity for PA-Processes

Jiri Srba

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning

11 Citationer (Scopus)

Abstract

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.

Originalsprog	Engelsk
Titel	Proceedings of 6th International Conference on Developments in Language Theory (DLT'02) : LNCS,
Forlag	Springer
Publikationsdato	2003
Udgave	2450
Sider	197-208
Status	Udgivet - 2003
Begivenhed	Undecidability of Weak Bisimilarity for PA-Processes - Varighed: 19 maj 2010 → …

Konference

Konference	Undecidability of Weak Bisimilarity for PA-Processes
Periode	19/05/2010 → …

Bibliografisk note

ISSN ; -

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Citationsformater

@inproceedings{17ded5f09c2e11db8ed6000ea68e967b,

title = "Undecidability of Weak Bisimilarity for PA-Processes",

abstract = "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.",

author = "Jiri Srba",

note = "ISSN ; -; Undecidability of Weak Bisimilarity for PA-Processes ; Conference date: 19-05-2010",

year = "2003",

language = "English",

pages = "197--208",

booktitle = "Proceedings of 6th International Conference on Developments in Language Theory (DLT'02)",

publisher = "Springer",

address = "Germany",

edition = "2450",

}

TY - GEN

T1 - Undecidability of Weak Bisimilarity for PA-Processes

AU - Srba, Jiri

N1 - ISSN ; -

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

M3 - Article in proceeding

SP - 197

EP - 208

BT - Proceedings of 6th International Conference on Developments in Language Theory (DLT'02)

PB - Springer

T2 - Undecidability of Weak Bisimilarity for PA-Processes

Y2 - 19 May 2010

ER -