Mathematics – Rings and Algebras
Scientific paper
2007-08-07
Mathematics
Rings and Algebras
17 pages
Scientific paper
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.
Kambites Mark
Render Elaine
No associations
LandOfFree
Rational semigroup automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rational semigroup automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rational semigroup automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-170494