G-automata, counter languages and the Chomsky hierarchy | NOVA. The University of Newcastle's Digital Repository

Home

Description	Size	Format
Author final version	92 KB	Adobe Acrobat PDF	View/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/931353

Title: G-automata, counter languages and the Chomsky hierarchy
Author/Creator: Elder, Murray
Description: 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 ℤⁿ-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for ℤⁿ is indexed.
Relation: Groups St Andrews 2005. Groups St Andrews 2005, Volume 1 (St Andrews, Scotland 30 July - 6 August, 2005) p. 313-318
Publisher Link: http://dx.doi.org/10.1017/CBO9780511721212.023
Date: 2007
Publisher: Cambridge University Press
Keyword(s): G-automaton; counter language; word problem for groups; Chomsky hierarchy
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/931353
Identifier: ISBN:9780521694698
Language: eng

19 Visitors

29 Hits

NOVA. The University of Newcastle's Digital Repository