2-nested simulation is not finitely equationally axiomatizable

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

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationSTACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsAfonso Ferreira, Horst Reichel
PublisherSpringer - Verlag
Pages39-50
Number of pages12
ISBN (Print)9783540416951
Publication statusPublished - 1 Jan 2001
Event18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 - Dresden, Germany
Duration: 15 Feb 200117 Feb 2001

Publication series

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

Conference

Conference18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001
CountryGermany
CityDresden
Period15/02/0117/02/01

    Fingerprint

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.