A Finite Axiomatisation of Finite-State Automata Using String Diagrams

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 not...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-02
Main Authors: Piedeleu, Robin, Zanasi, Fabio
Format: Article
Language:English
Subjects:
Axioms
Graphical representations
Strings
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.2211.16484