G-automata, counter languages and the Chomsky hierarchy

Elder, M

G-automata, counter languages and the Chomsky hierarchy

Elder, M

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of Groups St Andrews 2005, London Mathematical Society Lecture Note Series (339), eds C. Campbell, M. Quick, E. Robertson, G. Smith

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (115.41 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.identifier.citation	Proceedings of Groups St Andrews 2005, London Mathematical Society Lecture Note Series (339), eds C. Campbell, M. Quick, E. Robertson, G. Smith	en_US
dc.identifier.uri	http://hdl.handle.net/10453/101379
dc.description.abstract	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.	en_US
dc.relation.ispartof	Proceedings of Groups St Andrews 2005, London Mathematical Society Lecture Note Series (339), eds C. Campbell, M. Quick, E. Robertson, G. Smith	en_US
dc.title	G-automata, counter languages and the Chomsky hierarchy	en_US
dc.type	Conference Proceeding
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access

Abstract:

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:

http://hdl.handle.net/10453/101379