### 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 language | English |
---|---|

Title of host publication | Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings |

Editors | Ugo Montanari, Emo Welzl, Jose D. P. Rolim |

Publisher | Springer - Verlag |

Pages | 729-743 |

Number of pages | 15 |

ISBN (Print) | 9783540450221 |

Publication status | Published - 1 Jan 2000 |

Event | 27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland Duration: 9 Jul 2000 → 15 Jul 2000 |

### Publication series

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

Volume | 1853 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 27th International Colloquium on Automata, Languages and Programming, ICALP 2000 |
---|---|

Country | Switzerland |

City | Geneva |

Period | 9/07/00 → 15/07/00 |

### Fingerprint

### Cite this

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

}

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

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-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 -