Undecidable equivalences for basic parallel processes

Hans Hüttel; Naoki Kobayashi; Takashi Suto

doi:10.1016/j.ic.2008.12.011

Undecidable equivalences for basic parallel processes

Hans Hüttel^*, Naoki Kobayashi, Takashi Suto

^*Kontaktforfatter

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

4 Citationer (Scopus)

Abstract

The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that all the preorders and equivalences except bisimulation in Glabbeek's linear time-branching time spectrum are undecidable for BPP. The results are obtained by extending Hirshfeld's encoding of Minsky machines into BPP. We also show that those preorders and equivalences are undecidable even for a restriction of BPP to 2-labels.

Originalsprog	Engelsk
Tidsskrift	Information and Computation
Vol/bind	207
Udgave nummer	7
Sider (fra-til)	812-829
Antal sider	18
ISSN	0890-5401
DOI	https://doi.org/10.1016/j.ic.2008.12.011
Status	Udgivet - 1 jul. 2009

Adgang til dokumentet

10.1016/j.ic.2008.12.011

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

http://www.scopus.com/inward/record.url?scp=65649147585&partnerID=8YFLogxK

Citationsformater

@article{86295cfbcdb247fe8a3de74432e570cc,

title = "Undecidable equivalences for basic parallel processes",

abstract = "The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that all the preorders and equivalences except bisimulation in Glabbeek's linear time-branching time spectrum are undecidable for BPP. The results are obtained by extending Hirshfeld's encoding of Minsky machines into BPP. We also show that those preorders and equivalences are undecidable even for a restriction of BPP to 2-labels.",

author = "Hans H{\"u}ttel and Naoki Kobayashi and Takashi Suto",

year = "2009",

month = jul,

day = "1",

doi = "10.1016/j.ic.2008.12.011",

language = "English",

volume = "207",

pages = "812--829",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Academic Press",

number = "7",

}

TY - JOUR

T1 - Undecidable equivalences for basic parallel processes

AU - Hüttel, Hans

AU - Kobayashi, Naoki

AU - Suto, Takashi

PY - 2009/7/1

Y1 - 2009/7/1

N2 - The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that all the preorders and equivalences except bisimulation in Glabbeek's linear time-branching time spectrum are undecidable for BPP. The results are obtained by extending Hirshfeld's encoding of Minsky machines into BPP. We also show that those preorders and equivalences are undecidable even for a restriction of BPP to 2-labels.

AB - The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that all the preorders and equivalences except bisimulation in Glabbeek's linear time-branching time spectrum are undecidable for BPP. The results are obtained by extending Hirshfeld's encoding of Minsky machines into BPP. We also show that those preorders and equivalences are undecidable even for a restriction of BPP to 2-labels.

UR - http://www.scopus.com/inward/record.url?scp=65649147585&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2008.12.011

DO - 10.1016/j.ic.2008.12.011

M3 - Journal article

AN - SCOPUS:65649147585

SN - 0890-5401

VL - 207

SP - 812

EP - 829

JO - Information and Computation

JF - Information and Computation

IS - 7

ER -

Undecidable equivalences for basic parallel processes

Abstract

Adgang til dokumentet

AUB Link

Andre filer og links

Fingeraftryk

Citationsformater