An ω-Complete equational specification of interleaving

W. J. Fokkink, S. P. Luttik

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

Abstract

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
Pages729-743
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)
Volume1853
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Colloquium on Automata, Languages and Programming, ICALP 2000
CountrySwitzerland
CityGeneva
Period9/07/0015/07/00

Fingerprint

Interleaving
Specification
Specifications
Axioms
Parallel Composition
Chemical analysis
Paradigm
Valid
Standards

Cite this

Fokkink, W. J., & Luttik, S. P. (2000). An ω-Complete equational specification of interleaving. In U. Montanari, E. Welzl, & J. D. P. Rolim (Eds.), Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings (pp. 729-743). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1853). Springer - Verlag.
Fokkink, W. J. ; Luttik, S. P. / An ω-Complete equational specification of interleaving. Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. editor / Ugo Montanari ; Emo Welzl ; Jose D. P. Rolim. Springer - Verlag, 2000. pp. 729-743 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7502557f16794c8cbee8b0c4b0ad2e98,
title = "An ω-Complete equational specification of interleaving",
abstract = "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.",
author = "Fokkink, {W. J.} and Luttik, {S. P.}",
year = "2000",
month = "1",
day = "1",
language = "English",
isbn = "9783540450221",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer - Verlag",
pages = "729--743",
editor = "Ugo Montanari and Emo Welzl and Rolim, {Jose D. P.}",
booktitle = "Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings",

}

Fokkink, WJ & Luttik, SP 2000, An ω-Complete equational specification of interleaving. in U Montanari, E Welzl & JDP Rolim (eds), Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1853, Springer - Verlag, pp. 729-743, 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, Geneva, Switzerland, 9/07/00.

An ω-Complete equational specification of interleaving. / Fokkink, W. J.; Luttik, S. P.

Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. ed. / Ugo Montanari; Emo Welzl; Jose D. P. Rolim. Springer - Verlag, 2000. p. 729-743 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1853).

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

TY - GEN

T1 - An ω-Complete equational specification of interleaving

AU - Fokkink, W. J.

AU - Luttik, S. P.

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84974625258&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974625258&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9783540450221

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

SP - 729

EP - 743

BT - Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings

A2 - Montanari, Ugo

A2 - Welzl, Emo

A2 - Rolim, Jose D. P.

PB - Springer - Verlag

ER -

Fokkink WJ, Luttik SP. An ω-Complete equational specification of interleaving. In Montanari U, Welzl E, Rolim JDP, editors, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Springer - Verlag. 2000. p. 729-743. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).