Paper Info
Title
A String Diagrammatic Axiomatisation of Finite-State Automata
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.
Year
DOI
Venue
2021
10.1007/978-3-030-71995-1_24
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2021
Keywords
DocType
Volume
string diagrams, finite-state automata, symmetric monoidal category, complete axiomatisation
Conference
12650
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Robin Piedeleu1313.27
Fabio Zanasi211013.89