A cook’s tour of equational axiomatizations for prefix iteration

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

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Prefix iteration is a variation on the original binary version of the Kleene star operation P*Q, obtained by restricting the first argument to be an atomic action, and yields simple iterative behaviours that can be equationally characterized by means of finite collections of axioms. In this paper, we present axiomatic characterizations for a significant fragment of the notions of equivalence and preorder in van Glabbeek’s linear-time/branching-time spectrum over Milner’s basic CCS extended with prefix iteration. More precisely, we consider ready simulation, simulation, readiness, trace and language semantics, and provide complete (in)equational axiomatizations for each of these notions over BCCS with prefix iteration. All of the axiom systems we present are finite, if so is the set of atomic actions under consideration.

Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures - 1st International Conference, FoSSaCS 1998 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 1998, Proceedings
EditorsMaurice Nivat
PublisherSpringer - Verlag
Pages20-34
Number of pages15
ISBN (Print)3540643001, 9783540643005
Publication statusPublished - 1 Jan 1998
Event1st International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 1998 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 1998 - Lisbon, Portugal
Duration: 28 Mar 19984 Apr 1998

Publication series

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

Conference

Conference1st International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 1998 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 1998
CountryPortugal
CityLisbon
Period28/03/984/04/98

Fingerprint

Dive into the research topics of 'A cook’s tour of equational axiomatizations for prefix iteration'. Together they form a unique fingerprint.

Cite this