Tree Automata as Algebras: Minimisation and Determinisation

Abstract

We study a categorical generalisation of tree automata, as \(\Sigma\)-algebras for a fixed endofunctor \(\Sigma\) endowed with initial and final states. Under mild assumptions about the base category, we present a general minimisation algorithm for these automata. We build upon and extend an existing generalisation of the Nerode equivalence to a categorical setting, and relate it to the existence of minimal automata. Lastly, we show that generalised types of side-effects, such as non-determinism, can be captured by this framework, which leads to a general determinisation procedure.