An ω-Complete equational specification of interleaving

W. J. Fokkink, S. P. Luttik

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


We consider the process theory PA that includes an operation for parallel composition, based on the interleaving paradigm. We prove that the standard set of axioms of PA is not ω-complete by providing a set of axioms that are valid in PA, but not derivable from the standard ones. We prove that extending PA with this set yields an ω-complete specification, which is finite in a setting with finitely many actions.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
EditorsUgo Montanari, Emo Welzl, Jose D. P. Rolim
PublisherSpringer - Verlag
Number of pages15
ISBN (Print)9783540450221
Publication statusPublished - 1 Jan 2000
Event27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland
Duration: 9 Jul 200015 Jul 2000

Publication series

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


Conference27th International Colloquium on Automata, Languages and Programming, ICALP 2000


Dive into the research topics of 'An ω-Complete equational specification of interleaving'. Together they form a unique fingerprint.

Cite this