A String Diagrammatic Axiomatisation of Finite-State Automata

DOI10.1007/978-3-030-71995-1_24MaRDI QIDQ6350228arXivFDO

Authors Robin Piedeleu, Fabio Zanasi

Publication date 30 September 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-71995-1_24

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

arXiv classification

cs.FLcs.LOmath.CT

Abstract: We develop a fully diagrammatic approach to the theory of finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. Moreover, we provide an equational theory that completely axiomatises language equivalence in this new setting. This theory has two notable features. First, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks. Second, the proposed axiomatisation is finitary -- a result which is provably impossible to obtain for the one-dimensional syntax of regular expressions.

This page was built for publication: A String Diagrammatic Axiomatisation of Finite-State Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350228)