Book contents
- Frontmatter
- Contents
- Introduction
- Aspects of infinite permutation groups
- Self-similarity and branching in group theory
- On surface groups: motivating examples in combinatorial group theory
- Nilpotent p-algebras and factorized p-groups
- Classification of finite groups by the number of element centralizers
- Algorithmic use of the Mal'cev correspondence
- Minimal but inefficient presentations for semi-direct products of finite cyclic monoids
- The modular isomorphism problem for finite p-groups with a cyclic subgroup of index p2
- On one-generated formations
- New results on products of finite groups
- Radical locally finite T-groups
- Explicit tilting complexes for the Broué conjecture on 3-blocks
- Conjugacy classes of p-regular elements in p-solvable groups
- An algorithm for the unit group of the Burnside ring of a finite group
- Integral group ring of the first Mathieu simple group
- Embedding properties in direct products
- Malcev presentations for subsemigroups of groups — a survey
- Finite groups with extremal conditions on sizes of conjugacy classes and on degrees of irreducible characters
- Conjugacy class structure in simple algebraic groups
- On automorphisms of products of groups
- Linear groups with infinite central dimension
- G-automata, counter languages and the Chomsky hierarchy
- An embedding theorem for groups universally equivalent to free nilpotent groups
- Irreducible word problems in groups
- Recent growth results
G-automata, counter languages and the Chomsky hierarchy
Published online by Cambridge University Press: 07 May 2010
- Frontmatter
- Contents
- Introduction
- Aspects of infinite permutation groups
- Self-similarity and branching in group theory
- On surface groups: motivating examples in combinatorial group theory
- Nilpotent p-algebras and factorized p-groups
- Classification of finite groups by the number of element centralizers
- Algorithmic use of the Mal'cev correspondence
- Minimal but inefficient presentations for semi-direct products of finite cyclic monoids
- The modular isomorphism problem for finite p-groups with a cyclic subgroup of index p2
- On one-generated formations
- New results on products of finite groups
- Radical locally finite T-groups
- Explicit tilting complexes for the Broué conjecture on 3-blocks
- Conjugacy classes of p-regular elements in p-solvable groups
- An algorithm for the unit group of the Burnside ring of a finite group
- Integral group ring of the first Mathieu simple group
- Embedding properties in direct products
- Malcev presentations for subsemigroups of groups — a survey
- Finite groups with extremal conditions on sizes of conjugacy classes and on degrees of irreducible characters
- Conjugacy class structure in simple algebraic groups
- On automorphisms of products of groups
- Linear groups with infinite central dimension
- G-automata, counter languages and the Chomsky hierarchy
- An embedding theorem for groups universally equivalent to free nilpotent groups
- Irreducible word problems in groups
- Recent growth results
Summary
Abstract
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 ℤn-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for ℤn is indexed.
AMS Classification: 20F65, 20F10, 68Q45
Keywords: G-automaton; counter language; word problem for groups; Chomsky hierarchy
Introduction
In this article we compare the languages of G-automata, which include the set of counter languages, with the formal language classes of context-sensitive, indexed, context-free and regular. We prove in Theorem 6 that if the word problem of G is accepted by a machine in the class M then the language of any G-automaton is in the class M. It follows that the counter languages (languages of ℤn-automata) are context-sensitive. Moreover it follows that counter languages are indexed if and only if the word problem for ℤn is indexed.
The article is organized as follows. In Section 2 we define G-automata, linearly bounded automata, nested stack, stack, and pushdown automata, and the word problem for a finitely generated group. In Section 3 we prove the main theorem, and give the corollary that counter languages are indexed if and only if the word problem for ℤn is indexed for all n.
- Type
- Chapter
- Information
- Groups St Andrews 2005 , pp. 313 - 318Publisher: Cambridge University PressPrint publication year: 2007
- 2
- Cited by