Piedeleu, R;
Zanasi, F;
(2023)
A Finite Axiomatisation of Finite-State Automata Using String Diagrams.
Logical Methods in Computer Science
, 19
(1)
, Article 13. 10.46298/lmcs-19(1:13)2023.
Preview |
PDF
2211.16484.pdf - Published Version Download (811kB) | Preview |
Abstract
We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
| Type: | Article |
|---|---|
| Title: | A Finite Axiomatisation of Finite-State Automata Using String Diagrams |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.46298/lmcs-19(1:13)2023 |
| Publisher version: | https://doi.org/10.46298/lmcs-19(1:13)2023 |
| Language: | English |
| Additional information: | This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory |
| 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-pp.ucl.ac.uk/id/eprint/10167113 |
Archive Staff Only
 |
View Item |
