Open Access 2021 | OriginalPaper | Chapter
A String Diagrammatic Axiomatisation of Finite-State Automata
Authors : Robin Piedeleu, Fabio Zanasi
Published in: Foundations of Software Science and Computation Structures
Publisher: Springer International Publishing
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.