We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Automata with Counters that Recognize Word Problems of Free Products.
- Authors
Corson, Jon M.; Ross, Lance L.
- Abstract
An M-automaton is a finite automaton with a blind counter that mimics a monoid M. The finitely generated groups whose word problems (when viewed as formal languages) are accepted by M-automata play a central role in understanding the family 픏(M) of all languages accepted by M-automata. If G1 and G2 are finitely generated groups whose word problems are languages in 픏(M), in general, the word problem of the free product G1 * G2 is not necessarily in 픏(M). However, we show that if M is enlarged to the free product M*P2, where P2 is the polycyclic monoid of rank two, then this closure property holds. In fact, we show more generally that the special word problem of M1 * M2 lies in 픏(M * P2) whenever M1 and M2 are finitely generated monoids with special word problems in 픏(M * P2). We also observe that there is a monoid without zero, denoted by CF2, that can be used in place of P2 for this purpose. The monoid CF2 is the rank two case of what we call a monoid with right invertible basis and its Rees quotient by its maximal ideal is P2. The fundamental theory of monoids with right invertible bases is completely analogous to that of free groups, and thus they are very convenient to use. We also investigate the questions of whether there is a group that can be used instead of the monoid P2 in the above result and under what circumstances P1 (or the bicyclic monoid) is enough to do the job of P2.
- Subjects
AUTOMATION; FREE products (Group theory); PROBLEM solving; MONOIDS; APOLOGETICS
- Publication
International Journal of Foundations of Computer Science, 2015, Vol 26, Issue 1, p79
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054115500045