Abstract
We consider how the languages of G-automata compare with other formal language classes. We prove that if the word problem of G is accepted by a machine in the class then the language of any G-automaton is in the class. It follows that the so called counter languages (languages of ℤn-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for ℤn is indexed.
AMS Classification: 20F65, 20F10, 68Q45
Keywords: G-automaton; counter language; word problem for groups; Chomsky hierarchy
Introduction
In this article we compare the languages of G-automata, which include the set of counter languages, with the formal language classes of context-sensitive, indexed, context-free and regular. We prove in Theorem 6 that if the word problem of G is accepted by a machine in the class M then the language of any G-automaton is in the class M. It follows that the counter languages (languages of ℤn-automata) are context-sensitive. Moreover it follows that counter languages are indexed if and only if the word problem for ℤn is indexed.
The article is organized as follows. In Section 2 we define G-automata, linearly bounded automata, nested stack, stack, and pushdown automata, and the word problem for a finitely generated group. In Section 3 we prove the main theorem, and give the corollary that counter languages are indexed if and only if the word problem for ℤn is indexed for all n.