Undecidable equivalences for basic parallel processes

Hans Hüttel

doi:10.1007/3-540-57887-0_110

Undecidable equivalences for basic parallel processes

^*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

29 Citations (Scopus)

Abstract

Recent results show that strong bisimilarity is decidable for the class of Basic Parallel Processes (BPP), which corresponds to the subset of CCS definable using recursion, action prefixing, nondeterminism and the full merge operator. In this paper we examine all other equivalences in the linear/branching time hierarchy [12] and show that none of them are decidable for BPP.

Original language	English
Title of host publication	Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings
Editors	Masami Hagiya, John C. Mitchell
Number of pages	11
Publisher	Springer
Publication date	1994
Pages	454-464
ISBN (Print)	9783540578871
DOIs	https://doi.org/10.1007/3-540-57887-0_110
Publication status	Published - 1994
Event	2nd International Symposium on Theoretical Aspects of Computer Software, TACS 1994 - Sendai, Japan Duration: 19 Apr 1994 → 22 Apr 1994

Conference

Conference	2nd International Symposium on Theoretical Aspects of Computer Software, TACS 1994
Country/Territory	Japan
City	Sendai
Period	19/04/1994 → 22/04/1994
Sponsor	Tohoku University

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	789 LNCS
ISSN	0302-9743

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1994.

Access to Document

10.1007/3-540-57887-0_110

AUB Link

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

Cite this

Hüttel, Hans. / Undecidable equivalences for basic parallel processes. Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings. editor / Masami Hagiya ; John C. Mitchell. Springer, 1994. pp. 454-464 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 789 LNCS).

@inproceedings{d8e5967def6f4348a84f253bf000e652,

title = "Undecidable equivalences for basic parallel processes",

abstract = "Recent results show that strong bisimilarity is decidable for the class of Basic Parallel Processes (BPP), which corresponds to the subset of CCS definable using recursion, action prefixing, nondeterminism and the full merge operator. In this paper we examine all other equivalences in the linear/branching time hierarchy [12] and show that none of them are decidable for BPP.",

author = "Hans H{\"u}ttel",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 2nd International Symposium on Theoretical Aspects of Computer Software, TACS 1994 ; Conference date: 19-04-1994 Through 22-04-1994",

year = "1994",

doi = "10.1007/3-540-57887-0_110",

language = "English",

isbn = "9783540578871",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "454--464",

editor = "Masami Hagiya and Mitchell, {John C.}",

booktitle = "Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings",

address = "Germany",

}

Hüttel, H 1994, Undecidable equivalences for basic parallel processes. in M Hagiya & JC Mitchell (eds), Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 789 LNCS, pp. 454-464, 2nd International Symposium on Theoretical Aspects of Computer Software, TACS 1994, Sendai, Japan, 19/04/1994. https://doi.org/10.1007/3-540-57887-0_110

Undecidable equivalences for basic parallel processes. / Hüttel, Hans.
Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings. ed. / Masami Hagiya; John C. Mitchell. Springer, 1994. p. 454-464 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 789 LNCS).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Undecidable equivalences for basic parallel processes

AU - Hüttel, Hans

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1994.

PY - 1994

Y1 - 1994

N2 - Recent results show that strong bisimilarity is decidable for the class of Basic Parallel Processes (BPP), which corresponds to the subset of CCS definable using recursion, action prefixing, nondeterminism and the full merge operator. In this paper we examine all other equivalences in the linear/branching time hierarchy [12] and show that none of them are decidable for BPP.

AB - Recent results show that strong bisimilarity is decidable for the class of Basic Parallel Processes (BPP), which corresponds to the subset of CCS definable using recursion, action prefixing, nondeterminism and the full merge operator. In this paper we examine all other equivalences in the linear/branching time hierarchy [12] and show that none of them are decidable for BPP.

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

U2 - 10.1007/3-540-57887-0_110

DO - 10.1007/3-540-57887-0_110

M3 - Article in proceeding

AN - SCOPUS:84957683119

SN - 9783540578871

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 454

EP - 464

BT - Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings

A2 - Hagiya, Masami

A2 - Mitchell, John C.

PB - Springer

T2 - 2nd International Symposium on Theoretical Aspects of Computer Software, TACS 1994

Y2 - 19 April 1994 through 22 April 1994

ER -

Hüttel H. Undecidable equivalences for basic parallel processes. In Hagiya M, Mitchell JC, editors, Theoretical Aspects of Computer Software - International Symposium TACS 1994, Proceedings. Springer. 1994. p. 454-464. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 789 LNCS). doi: 10.1007/3-540-57887-0_110

Undecidable equivalences for basic parallel processes

Abstract

Conference

Bibliographical note

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this