Semigroup automata with rational initial and terminal sets
We consider a natural extension of the usual definition of M-automata (also known as extended automata or valence automata) which permits the automaton to utilise more of the structure of each monoid, and additionally allows us to define S-automata for S an arbitrary semigroup. In the monoid case, the resulting automata are equivalent to the valence automata with rational target sets which arise in the theory of regulated rewriting systems. We study these automata in the case where the register semigroup is completely simple or completely 0-simple, obtaining a complete characterisation of the classes of languages corresponding to such semigroups, in terms of their maximal subgroups. In the process, we obtain a number of results about rational subsets of Rees matrix semigroups which are likely to be of independent interest.