2-nested simulation is not finitely equationally axiomatizable

Luca Aceto; Wan Fokkink; Anna Ingólfsdóttir

2-nested simulation is not finitely equationally axiomatizable

Luca Aceto
, Wan Fokkink
, Anna Ingólfsdóttir

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

2-nested simulation was introduced by Groote and Vaan-drager [10] as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek [8], 2-nested simulation is one of the few equivalences for which no finite equational axiomatization is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation.

Original language	English
Title of host publication	STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Editors	Afonso Ferreira, Horst Reichel
Publisher	Springer - Verlag
Pages	39-50
Number of pages	12
ISBN (Print)	9783540416951
Publication status	Published - 1 Jan 2001
Event	18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 - Dresden, Germany Duration: 15 Feb 2001 → 17 Feb 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2010
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001
Country/Territory	Germany
City	Dresden
Period	15/02/01 → 17/02/01

UN SDGs

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

SDG 7 Affordable and Clean Energy

Persistent URL (handle)

Persistent link

Cite this

Aceto, L., Fokkink, W., & Ingólfsdóttir, A. (2001). 2-nested simulation is not finitely equationally axiomatizable. In A. Ferreira, & H. Reichel (Eds.), STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 39-50). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2010). Springer - Verlag.

Aceto, Luca ; Fokkink, Wan ; Ingólfsdóttir, Anna. / 2-nested simulation is not finitely equationally axiomatizable. STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. editor / Afonso Ferreira ; Horst Reichel. Springer - Verlag, 2001. pp. 39-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d62de0a84f124f11998360db8839952f,

title = "2-nested simulation is not finitely equationally axiomatizable",

abstract = "2-nested simulation was introduced by Groote and Vaan-drager [10] as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek [8], 2-nested simulation is one of the few equivalences for which no finite equational axiomatization is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation.",

author = "Luca Aceto and Wan Fokkink and Anna Ing{\'o}lfsd{\'o}ttir",

year = "2001",

month = jan,

day = "1",

language = "English",

isbn = "9783540416951",

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

publisher = "Springer - Verlag",

pages = "39--50",

editor = "Afonso Ferreira and Horst Reichel",

booktitle = "STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

note = "18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 ; Conference date: 15-02-2001 Through 17-02-2001",

}

Aceto, L, Fokkink, W & Ingólfsdóttir, A 2001, 2-nested simulation is not finitely equationally axiomatizable. in A Ferreira & H Reichel (eds), STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2010, Springer - Verlag, pp. 39-50, 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001, Dresden, Germany, 15/02/01.

2-nested simulation is not finitely equationally axiomatizable. / Aceto, Luca; Fokkink, Wan; Ingólfsdóttir, Anna.
STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. ed. / Afonso Ferreira; Horst Reichel. Springer - Verlag, 2001. p. 39-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2010).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - 2-nested simulation is not finitely equationally axiomatizable

AU - Aceto, Luca

AU - Fokkink, Wan

AU - Ingólfsdóttir, Anna

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 2-nested simulation was introduced by Groote and Vaan-drager [10] as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek [8], 2-nested simulation is one of the few equivalences for which no finite equational axiomatization is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation.

AB - 2-nested simulation was introduced by Groote and Vaan-drager [10] as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek [8], 2-nested simulation is one of the few equivalences for which no finite equational axiomatization is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation.

UR - https://www.scopus.com/pages/publications/84957099297

UR - https://www.scopus.com/pages/publications/84957099297#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:84957099297

SN - 9783540416951

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

SP - 39

EP - 50

BT - STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

A2 - Ferreira, Afonso

A2 - Reichel, Horst

PB - Springer - Verlag

T2 - 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001

Y2 - 15 February 2001 through 17 February 2001

ER -

Aceto L, Fokkink W, Ingólfsdóttir A. 2-nested simulation is not finitely equationally axiomatizable. In Ferreira A, Reichel H, editors, STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer - Verlag. 2001. p. 39-50. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

2-nested simulation is not finitely equationally axiomatizable

Abstract

Publication series

Conference

UN SDGs

Persistent URL (handle)

Other files and links

Fingerprint

Cite this