Automatic group

From Groupprops
Jump to: navigation, search

Definition

An automatic group is a finitely generated group satisfying the following equivalent conditions:

  1. There exists a finite generating set with respect to which the group possesses an automatic structure.
  2. For every finite generating set, the group possesses an automatic structure with respect to that generating set.
This article defines a group property: a property that can be evaluated to true/false for any given group, invariant under isomorphism
View a complete list of group properties
VIEW RELATED: Group property implications | Group property non-implications |Group metaproperty satisfactions | Group metaproperty dissatisfactions | Group property satisfactions | Group property dissatisfactions

Relation with other properties

Stronger properties

Property Meaning Proof of implication Proof of strictness (reverse implication failure) Intermediate notions
biautomatic group |FULL LIST, MORE INFO
finite group |FULL LIST, MORE INFO
word-hyperbolic group word-hyperbolic implies automatic automatic not implies word-hyperbolic |FULL LIST, MORE INFO
finitely generated free group |FULL LIST, MORE INFO

Weaker properties

Property Meaning Proof of implication Proof of strictness (reverse implication failure) Intermediate notions
group satisfying a quadratic isoperimetric inequality |FULL LIST, MORE INFO
group satisfying a polynomial isoperimetric inequality Group satisfying a quadratic isoperimetric inequality|FULL LIST, MORE INFO
group with polynomial-time solvable word problem |FULL LIST, MORE INFO
group with solvable word problem Group satisfying a polynomial isoperimetric inequality, Group satisfying a quadratic isoperimetric inequality, Group with nondeterministic polynomial-time solvable word problem, Group with polynomial-time solvable word problem|FULL LIST, MORE INFO