Recognisable languages over free algebras

This thesis considers notions of recognisability for languages over (universal) algebras. The main motivation here is the body of work on recognisable languages over the free monoid, which in particular connects several, equivalent, approaches. The free monoid X^* on a set X consists of all finite strings of elements of X; these are thought of as words, and hence a subset of X^* is known as a language (i.e. a collection of words). The term is then used for a subset of any (free) algebra.

Our first approach to recognisability is via finite index of syntactic congruences; the latter may be defined for any kind of algebra. We consider how to define syntactic congruences in the most efficient way: absolutely, or with regard to a particular class of algebras or languages. We give examples where only finitely many terms are needed to determine syntactic congruences. For a particular class of free algebras we find an infinite list of terms, each built from the previous, and give an example of a language such that we need to check terms of every kind. Using syntactic congruences we consider closure properties of recognisable languages. We give many examples, including critical examples of languages that are themselves free algebras (in some sense) but are contained in the free inverse monoid.

Our second approach is in the context of unary monoids. We introduce a new kind of formal machine we call a +-automaton. Our main result in this regard is to show that a language over a free unary monoid has syntactic congruence of finite index if and only if it is recognised by a +-automaton. This result exactly parallels the well known result for languages over free monoids.