automatic group

Let G be a finitely generated group. Let A be a finite generating set for G under inversesMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.

G is an automatic groupMathworldPlanetmath if there is a languagePlanetmathPlanetmath LA* and a surjective map f:LG such that

  • L can be checked by a finite automaton (

  • The language of all convolutions of x,y where f(x)=f(y) can be checked by a

  • For each aA, the language of all convolutions of x,y where f(x).a=f(y) can be checked by a

(A,L) is said to be an automatic structure for G.

Note that by taking a finitely generatedMathworldPlanetmath semigroupPlanetmathPlanetmath S, and some finite generating set A, these conditions define an automatic semigroup.

Title automatic group
Canonical name AutomaticGroup
Date of creation 2013-03-22 14:16:54
Last modified on 2013-03-22 14:16:54
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 7
Author mathcam (2727)
Entry type Definition
Classification msc 20F10
Related topic AutomaticPresentation
Defines automatic semigroup
Defines automatic structure