Rational semigroup automata
| dc.creator | Render, Elaine | |
| dc.creator | Kambites, Mark | |
| dc.date | 2007-08-07 | |
| dc.date.accessioned | 2026-07-07T08:22:35Z | |
| dc.date.available | 2026-07-07T08:22:35Z | |
| dc.description | We show that for any monoid M, the family of languages accepted by M-automata (or equivalently, generated by regular valence grammars over M) is completely determined by that part of M which lies outside the maximal ideal. Hence, every such family arises as the family of languages accepted by N-automata where N is a simple or 0-simple monoid. A consequence is that every such family is either the class of regular languages, contains all the blind one-counter languages, or is the family of languages accepted by G-automata for G a non-locally-finite torsion group. We consider a natural extension of the usual definition which permits the automata to utilise more of the structure of each monoid, and also 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 the case that 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 may be of independent interest. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/0708.0947 | |
| dc.identifier | http://arxiv.org/abs/0708.0947 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/135704 | |
| dc.subject | Rings and Algebras | |
| dc.subject | 20M35, 68Q70 | |
| dc.title | Rational semigroup automata | |
| dc.type | text |