A Finite Axiomatisation of Finite-State Automata Using String Diagrams

Robin Piedeleu; Fabio Zanasi

doi:10.46298/lmcs-19(1:13)2023

Robin Piedeleu ; Fabio Zanasi - A Finite Axiomatisation of Finite-State Automata Using String Diagrams

lmcs:10400 - Logical Methods in Computer Science, February 15, 2023, Volume 19, Issue 1 - https://doi.org/10.46298/lmcs-19(1:13)2023

A Finite Axiomatisation of Finite-State Automata Using String DiagramsArticle

Authors: Robin Piedeleu ¹; Fabio Zanasi ^1,²

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.

https://doi.org/10.46298/lmcs-19(1:13)2023

Source: arXiv.org:2211.16484

Volume: Volume 19, Issue 1

Published on: February 15, 2023

Accepted on: November 30, 2022

Submitted on: November 30, 2022

Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory

Licence: Attribution 4.0 International (CC BY 4.0)