1 Search Results for "Belder, Astrid"

Document
DOI: 10.4230/LIPIcs.CALCO.2019.11
Sequencing and Intermediate Acceptance: Axiomatisation and Decidability of Bisimilarity

Authors: Astrid Belder, Bas Luttik, and Jos Baeten

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
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.
Cite as

Astrid Belder, Bas Luttik, and Jos Baeten. Sequencing and Intermediate Acceptance: Axiomatisation and Decidability of Bisimilarity. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{belder_et_al:LIPIcs.CALCO.2019.11,
  author =	{Belder, Astrid and Luttik, Bas and Baeten, Jos},
  title =	{{Sequencing and Intermediate Acceptance: Axiomatisation and Decidability of Bisimilarity}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.11},
  URN =		{urn:nbn:de:0030-drops-114390},
  doi =		{10.4230/LIPIcs.CALCO.2019.11},
  annote =	{Keywords: Sequencing, Sequential composition, Bisimilarity, Axiomatisation, Decidability}
}
  • Refine by Author
  • 1 Baeten, Jos
  • 1 Belder, Astrid
  • 1 Luttik, Bas

  • Refine by Classification
  • 1 Theory of computation → Process calculi

  • Refine by Keyword
  • 1 Axiomatisation
  • 1 Bisimilarity
  • 1 Decidability
  • 1 Sequencing
  • 1 Sequential composition

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact