The Equational Theory of Prebisimilarity over Basic CCS with Divergence

L. Aceto; S. Capobianco; A. Ingolfsdottir; B. Luttik

doi:10.1016/j.ipl.2008.05.019

The Equational Theory of Prebisimilarity over Basic CCS with Divergence

L. Aceto, S. Capobianco, A. Ingolfsdottir, B. Luttik

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Ω. It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language; this study proves that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, it is shown that prebisimilarity is not finitely based over basic CCS with the divergent process Ω when the set of actions is finite and nonempty. © 2008 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	284-289
Journal	Information Processing Letters
Volume	108
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2008.05.019
Publication status	Published - 2009

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.ipl.2008.05.019

Persistent URL (handle)

Persistent link

Cite this

@article{825f92d7467b403f9d8988cca13a037d,

title = "The Equational Theory of Prebisimilarity over Basic CCS with Divergence",

abstract = "This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Ω. It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language; this study proves that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, it is shown that prebisimilarity is not finitely based over basic CCS with the divergent process Ω when the set of actions is finite and nonempty. {\textcopyright} 2008 Elsevier B.V. All rights reserved.",

author = "L. Aceto and S. Capobianco and A. Ingolfsdottir and B. Luttik",

year = "2009",

doi = "10.1016/j.ipl.2008.05.019",

language = "English",

volume = "108",

pages = "284--289",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - The Equational Theory of Prebisimilarity over Basic CCS with Divergence

AU - Aceto, L.

AU - Capobianco, S.

AU - Ingolfsdottir, A.

AU - Luttik, B.

PY - 2009

Y1 - 2009

N2 - This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Ω. It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language; this study proves that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, it is shown that prebisimilarity is not finitely based over basic CCS with the divergent process Ω when the set of actions is finite and nonempty. © 2008 Elsevier B.V. All rights reserved.

AB - This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Ω. It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language; this study proves that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, it is shown that prebisimilarity is not finitely based over basic CCS with the divergent process Ω when the set of actions is finite and nonempty. © 2008 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.ipl.2008.05.019

DO - 10.1016/j.ipl.2008.05.019

M3 - Article

SN - 0020-0190

VL - 108

SP - 284

EP - 289

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

The Equational Theory of Prebisimilarity over Basic CCS with Divergence

Abstract

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this