01 October 2020, 14:00, online

Speaker

Robin Piedeleu, University College London

Title

A diagrammatic axiomatisation of finite-state automata

Abstract

In this talk I will present a fully diagrammatic approach to the theory of finite-state automata, based on reinterpreting their usual state-transition graphical representation as string diagrams. Moreover, I will give an equational theory that completely axiomatises language equivalence in this new setting. The proposed axiomatisation is finitary--- a result which is provably impossible to obtain for the usual one-dimensional syntax of regular expressions. These results are the product of joint work with Fabio Zanasi.