Undecidable equivalences for basic process algebra

Jan Friso Groote; Hans Hüttel

doi:10.1006/inco.1994.1101

Undecidable equivalences for basic process algebra

Jan Friso Groote, Hans Hüttel

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

41 Citations (Scopus)

Abstract

A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context-free grammars generating the ε-free context-free languages. Huynh and Tian (Technical Report UTDCS-31-90, University of Texas at Dallas, 1990) have shown that readiness and failure equivalence are undecidable for BPA processes. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for normed BPA processes.

Original language	English
Journal	Information and Computation
Volume	115
Issue number	2
Pages (from-to)	354-371
Number of pages	18
ISSN	0890-5401
DOIs	https://doi.org/10.1006/inco.1994.1101
Publication status	Published - Dec 1994

Access to Document

10.1006/inco.1994.1101

AUB Link

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

Cite this

@article{89c7ed00bf0542468f05393c5033c0c2,

title = "Undecidable equivalences for basic process algebra",

abstract = "A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context-free grammars generating the ε-free context-free languages. Huynh and Tian (Technical Report UTDCS-31-90, University of Texas at Dallas, 1990) have shown that readiness and failure equivalence are undecidable for BPA processes. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for normed BPA processes.",

author = "Groote, {Jan Friso} and Hans H{\"u}ttel",

year = "1994",

month = dec,

doi = "10.1006/inco.1994.1101",

language = "English",

volume = "115",

pages = "354--371",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Academic Press",

number = "2",

}

TY - JOUR

T1 - Undecidable equivalences for basic process algebra

AU - Groote, Jan Friso

AU - Hüttel, Hans

PY - 1994/12

Y1 - 1994/12

N2 - A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context-free grammars generating the ε-free context-free languages. Huynh and Tian (Technical Report UTDCS-31-90, University of Texas at Dallas, 1990) have shown that readiness and failure equivalence are undecidable for BPA processes. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for normed BPA processes.

AB - A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context-free grammars generating the ε-free context-free languages. Huynh and Tian (Technical Report UTDCS-31-90, University of Texas at Dallas, 1990) have shown that readiness and failure equivalence are undecidable for BPA processes. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for normed BPA processes.

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

U2 - 10.1006/inco.1994.1101

DO - 10.1006/inco.1994.1101

M3 - Journal article

AN - SCOPUS:0000788107

SN - 0890-5401

VL - 115

SP - 354

EP - 371

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -

Undecidable equivalences for basic process algebra

Abstract

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this