Piedeleu, R;
Zanasi, F;
(2021)
A String Diagrammatic Axiomatisation of Finite-State Automata.
In: Kiefer, S and Tasson, C, (eds.)
Foundations of Software Science and Computation Structures.
(pp. pp. 469-489).
Springer
Preview |
Text
Piedeleu-Zanasi2021_Chapter_AStringDiagrammaticAxiomatisat.pdf - Published Version Download (431kB) | 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— a result which is provably impossible for the one-dimensional syntax of regular expressions. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
| Type: | Proceedings paper |
|---|---|
| Title: | A String Diagrammatic Axiomatisation of Finite-State Automata. |
| Event: | International Conference on Foundations of Software Science and Computation Structures |
| ISBN-13: | 978-3-030-71994-4 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://doi.org/10.1007/978-3-030-71995-1 |
| Language: | English |
| Additional information: | This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. |
| Keywords: | string diagrams; finite-state automata; symmetric monoidal category; complete axiomatisation |
| 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/10126196 |
Archive Staff Only
 |
View Item |
