Schmid, T;
Rot, J;
Silva, A;
(2021)
On Star Expressions and Completeness Theorems.
In:
Proceedings: 37th Conference on Mathematical Foundations of Programming Semantics.
(pp. pp. 242-259).
Preview |
Text
Silva_2106.08074v2.pdf Download (237kB) | Preview |
Abstract
An open problem posed by Milner asks for a proof that a certain axiomatisation, which Milner showed is sound with respect to bisimilarity for regular expressions, is also complete. One of the main difficulties of the problem is the lack of a full Kleene theorem, since there are automata that can not be specified, up to bisimilarity, by an expression. Grabmayer and Fokkink (2020) characterise those automata that can be expressed by regular expressions without the constant 1, and use this characterisation to give a positive answer to Milner's question for this subset of expressions. In this paper, we analyse Grabmayer and Fokkink's proof of completeness from the perspective of universal coalgebra, and thereby give an abstract account of their proof method. We then compare this proof method to another approach to completeness proofs from coalgebraic language theory. This culminates in two abstract proof methods for completeness, what we call the local and global approaches, and a description of when one method can be used in place of the other.
| Type: | Proceedings paper |
|---|---|
| Title: | On Star Expressions and Completeness Theorems |
| Event: | MFPS 2021: 37th Conference on Mathematical Foundations of Programming Semantics |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4204/EPTCS.351.15 |
| Publisher version: | http://dx.doi.org/10.4204/EPTCS.351.15 |
| Language: | English |
| Additional information: | © T. Schmid, J. Rot, & A. Silva This work is licensed under the Creative Commons Attribution License. |
| Keywords: | Regular expressions, bisimulation, program semantics, coalgebra. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10130031 |
Archive Staff Only
 |
View Item |
