License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2021.16
URN: urn:nbn:de:0030-drops-153712
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15371/
Go to the corresponding LIPIcs Volume Portal

Grabmayer, Clemens

A Coinductive Version of Milner’s Proof System for Regular Expressions Modulo Bisimilarity

pdf-format:
LIPIcs-CALCO-2021-16.pdf (0.9 MB)

Abstract

By adapting Salomaa’s complete proof system for equality of regular expressions under the language semantics, Milner (1984) formulated a sound proof system for bisimilarity of regular expressions under the process interpretation he introduced. He asked whether this system is complete. Proof-theoretic arguments attempting to show completeness of this equational system are complicated by the presence of a non-algebraic rule for solving fixed-point equations by using star iteration.
We characterize the derivational power that the fixed-point rule adds to the purely equational part Mil- of Milner’s system Mil: it corresponds to the power of coinductive proofs over Mil- that have the form of finite process graphs with the loop existence and elimination property LEE. We define a variant system cMil by replacing the fixed-point rule in Mil with a rule that permits LEE-shaped circular derivations in Mil- from previously derived equations as a premise. With this rule alone we also define the variant system CLC for combining LEE-shaped coinductive proofs over Mil-. We show that both cMil and CLC have proof interpretations in Mil, and vice versa. As this correspondence links, in both directions, derivability in Mil with derivation trees of process graphs, it widens the space for graph-based approaches to finding a completeness proof of Milner’s system.

BibTeX - Entry

@InProceedings{grabmayer:LIPIcs.CALCO.2021.16,
  author =	{Grabmayer, Clemens},
  title =	{{A Coinductive Version of Milner’s Proof System for Regular Expressions Modulo Bisimilarity}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15371},
  URN =		{urn:nbn:de:0030-drops-153712},
  doi =		{10.4230/LIPIcs.CALCO.2021.16},
  annote =	{Keywords: regular expressions, process theory, bisimilarity, coinduction, proof theory}
}

Keywords: regular expressions, process theory, bisimilarity, coinduction, proof theory
Collection: 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)
Issue Date: 2021
Date of publication: 08.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI