G-automata, counter languages and the Chomsky hierarchy

Publication Type:
Conference Proceeding
Proceedings of Groups St Andrews 2005, London Mathematical Society Lecture Note Series (339), eds C. Campbell, M. Quick, E. Robertson, G. Smith
Full metadata record
Files in This Item:
Filename Description Size
Gautomata.pdfAccepted Manuscript version115.41 kB
Adobe PDF
We consider how the languages of $G$-automata compare with other formal language classes. We prove that if the word problem of a group $G$ is accepted by a machine in the class $\mathcal M$ then the language of any $G$-automaton is in the class $\mathcal M$. It follows that the so called {\emph counter languages} (languages of $\mathbb Z^n$-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for $\mathbb Z^n$ is indexed.
Please use this identifier to cite or link to this item: