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

^*Corresponding author for this work

Research output: Contribution to journal › Journal article › Research › peer-review

4 Citations (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.

Original language	English
Journal	Information and Computation
Volume	207
Issue number	7
Pages (from-to)	812-829
Number of pages	18
ISSN	0890-5401
DOIs	https://doi.org/10.1016/j.ic.2008.12.011
Publication status	Published - 1 Jul 2009

Access to Document

10.1016/j.ic.2008.12.011

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@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

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this