Nested semantics over finite trees are equationally hard

L. Aceto; W.J. Fokkink; R.J. van Glabbeek; A. Ingólfsdóttir

doi:10.1016/j.ic.2004.02.001

Nested semantics over finite trees are equationally hard

L. Aceto, W.J. Fokkink, R.J. van Glabbeek, A. Ingólfsdóttir

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

Abstract

This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. © 2004 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	203-232
Journal	Information and Computation
Volume	191
Issue number	2
DOIs	https://doi.org/10.1016/j.ic.2004.02.001
Publication status	Published - 2004

Bibliographical note

DBLP:journals/iandc/AcetoFGI04

UN SDGs

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

Access to Document

10.1016/j.ic.2004.02.001

Persistent URL (handle)

Persistent link

Cite this

@article{dea1fd5a2e11498eaab9ec7159274132,

title = "Nested semantics over finite trees are equationally hard",

abstract = "This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. {\textcopyright} 2004 Elsevier Inc. All rights reserved.",

author = "L. Aceto and W.J. Fokkink and {van Glabbeek}, R.J. and A. Ing{\'o}lfsd{\'o}ttir",

note = "DBLP:journals/iandc/AcetoFGI04 ",

year = "2004",

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

language = "English",

volume = "191",

pages = "203--232",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Nested semantics over finite trees are equationally hard

AU - Aceto, L.

AU - Fokkink, W.J.

AU - van Glabbeek, R.J.

AU - Ingólfsdóttir, A.

N1 - DBLP:journals/iandc/AcetoFGI04

PY - 2004

Y1 - 2004

N2 - This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. © 2004 Elsevier Inc. All rights reserved.

AB - This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. © 2004 Elsevier Inc. All rights reserved.

U2 - 10.1016/j.ic.2004.02.001

DO - 10.1016/j.ic.2004.02.001

M3 - Article

SN - 0890-5401

VL - 191

SP - 203

EP - 232

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -

Nested semantics over finite trees are equationally hard

Abstract

Bibliographical note

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this