G-automata, counter languages and the Chomsky hierarchy

Campbell, C. M. and Quick, M. R. and Robertson, E. F. and Smith, G. C. (2010) G-automata, counter languages and the Chomsky hierarchy. Proceedings of Groups St Andrews 2005, London Math. Soc. Lecture Note Ser. 339 (2007)., 1 . pp. 313-318.

PDF - Accepted Version
Download (92Kb) | Preview


    We consider how the languages of G-automata compare with other formal language classes. We prove that if the word prob- lem of G is accepted by a machine in the class M then the language of any G-automaton is in the classM. It follows that the so called counter languages (languages of Zn-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for Zn is indexed.

    Item Type: Article
    Subjects: 20-xx Group theory and generalizations
    Faculty: UNSPECIFIED
    Depositing User: Dr Murray Elder
    Date Deposited: 17 Sep 2012 10:42
    Last Modified: 17 Sep 2012 10:42

    Actions (login required)

    View Item