Sequencing and intermediate acceptance: axiomatisation and decidability of bisimilarity

Astrid Belder, Bas Luttik, Jos Baeten

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Downloads (Pure)

Samenvatting

The Theory of Sequential Processes includes deadlock, successful termination, action prefixing, alternative and sequential composition. Intermediate acceptance, which is important for the integration of classical automata theory, can be expressed through a combination of alternative composition and successful termination. Recently, it was argued that complications arising from the interplay between intermediate acceptance and sequential composition can be eliminated by replacing sequential composition by sequencing. In this paper we study the equational theory of the recursion-free fragment of the resulting process theory modulo bisimilarity, proving that it is not finitely based, but does afford a ground-complete axiomatisation if a unary auxiliary operator is added. Furthermore, we prove that bisimilarity is decidable for processes definable by means of a finite guarded recursive specification over the process theory.

Originele taal-2Engels
Titel8th Conference on Algebra and Coalgebra in Computer Science, CALCO 2019
RedacteurenMarkus Roggenbach, Ana Sokolova
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's22
ISBN van elektronische versie978-3-95977-120-7
DOI's
StatusGepubliceerd - nov 2019
Evenement8th Conference on Algebra and Coalgebra in Computer Science, CALCO 2019 - London, Verenigd Koninkrijk
Duur: 3 jun 20196 jun 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume139
ISSN van geprinte versie1868-8969

Congres

Congres8th Conference on Algebra and Coalgebra in Computer Science, CALCO 2019
LandVerenigd Koninkrijk
StadLondon
Periode3/06/196/06/19

Vingerafdruk Duik in de onderzoeksthema's van 'Sequencing and intermediate acceptance: axiomatisation and decidability of bisimilarity'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Belder, A., Luttik, B., & Baeten, J. (2019). Sequencing and intermediate acceptance: axiomatisation and decidability of bisimilarity. In M. Roggenbach, & A. Sokolova (editors), 8th Conference on Algebra and Coalgebra in Computer Science, CALCO 2019 [11] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 139). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CALCO.2019.11