POPL 2027 (series) / POPL Research Papers /
The equational theory of rational string-to-string functions
We give a sound and complete equational axiomatisation of the rational string-to-string functions, which can be seen as a transducer counterpart of the classical axiomatisations of regular languages by Salomaa [JACM’66], Krob [TCS’91], Bloom and Ésik [MSCS’93], and Kozen [IC’94]. The axioms are stated over a compositional, algebraic syntax for rational functions, namely the rational fragment of the syntax for regular functions introduced by Bojańczyk, Daviaud and Krishna [LICS’18]. The axiomatisation is finitary, as it consists of finitely many uniform families of axioms, each parameterised by the types involved. It is also purely equational: it consists only of equations, with no implication rules.