A Finite Axiomatisation of Finite-State Automata Using String Diagrams

11/29/2022
by   Robin Piedeleu, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset