1 Search Results for "Yu, TingTing"


Document
Canonical Solutions to Recursive Equations and Completeness of Equational Axiomatisations

Authors: Xinxin Liu and TingTing Yu

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)


Abstract
In this paper we prove completeness of four axiomatisations for finite-state behaviours with respect to behavioural equivalences at various τ-abstract levels: branching congruence, delay congruence, η-congruence, and weak congruence. Instead of merging guarded recursive equations, which was the approach originally used by Robin Milner and has since become the standard strategy for proving completeness results of this kind, in this work we take a new approach by solving guarded recursive equations with canonical solutions which are those with the fewest reachable states. The new strategy allows uniform treatment of the axiomatisations with respect to different behavioural equivalences.

Cite as

Xinxin Liu and TingTing Yu. Canonical Solutions to Recursive Equations and Completeness of Equational Axiomatisations. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.CONCUR.2020.35,
  author =	{Liu, Xinxin and Yu, TingTing},
  title =	{{Canonical Solutions to Recursive Equations and Completeness of Equational Axiomatisations}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.35},
  URN =		{urn:nbn:de:0030-drops-128479},
  doi =		{10.4230/LIPIcs.CONCUR.2020.35},
  annote =	{Keywords: Bisimulation, Congruence, Axiomatisation, Soundness and Completeness}
}
  • Refine by Author
  • 1 Liu, Xinxin
  • 1 Yu, TingTing

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

  • Refine by Keyword
  • 1 Axiomatisation
  • 1 Bisimulation
  • 1 Congruence
  • 1 Soundness and Completeness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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