We consider a natural extension to the definition of Mautomata 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 Sautomata 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 contextfree 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 0simple 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) 

 semigroups
 automata
 rational subsets
Rational Monoid and Semigroup Automata
Render, E. (Author). 31 Dec 2010
Student thesis: Phd