Open Research Newcastle
Browse

G-automata, counter languages and the Chomsky hierarchy

Download (92.4 kB)
conference contribution
posted on 2025-05-08, 13:38 authored by Murray Elder
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.

History

Source title

Groups St Andrews 2005, Volume 1

Name of conference

Groups St Andrews 2005

Location

St Andrews, Scotland

Start date

2005-07-30

End date

2005-08-06

Pagination

313-318

Publisher

Cambridge University Press

Place published

Cambridge, UK

Language

  • en, English

College/Research Centre

Faculty of Science and Information Technology

School

School of Mathematical and Physical Sciences

Usage metrics

    Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC