Rational Monoid and Semigroup Automata

Abstract

We consider a natural extension to the definition of M-automata which allows the automatonto make use of more of the structure of the monoid M, and by removing the reliance onan identity element, allows the definition of S-automata for S an arbitrary semigroup.In the case of monoids, the resulting automata are equivalent to valence automata with rational target setswhich arise in the theory of regulated rewriting. We focus on the polycyclic monoids, and show that forpolycyclic monoids of rank 2 or more they accept precisely the context-free languages. The case of the bicyclicmonoid is also considered. In the process we prove a number of interesting results about rational subsets inpolycyclic monoids; as a consequence we prove thedecidability of the rational subset membership problem, and theclosure of the class of rational subsets under intersection andcomplement.In the case of semigroups, we consider the important class of completely simpleand completely 0-simple semigroups,obtaining a complete characterisation of the classes of languagescorresponding to such semigroups, in terms of their maximal subgroups. Inthe process, we obtain a number of interesting results about rational subsets of Reesmatrix semigroups.

Date of Award	31 Dec 2010
Original language	English
Awarding Institution	The University of Manchester
Supervisor	Alexandre Borovik (Supervisor) & Mark Kambites (Supervisor)