PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
automatic group (Definition)

Let $ G$ be a finitely generated group. Let $ A$ be a finite generating set for $ G$ closed under inverses.

$ G$ is an automatic group if there is a language $ L\subseteq A^*$ and a surjective map $ f:L\rightarrow G$ 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 finite automaton
  • For each $ a\in A$, the language of all convolutions of $ x,y$ where $ f(x).a=f(y)$ can be checked by a finite automaton

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

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



"automatic group" is owned by mathcam. [ owner history (1) ]
(view preamble)

View style:

See Also: automatic presentation

Also defines:  automatic semigroup, automatic structure
Log in to rate this entry.
(view current ratings)

Cross-references: semigroup, finitely generated, convolutions, map, surjective, language, inverses, generating set, finite, finitely generated group
There are 2 references to this entry.

This is version 4 of automatic group, born on 2004-03-29, modified 2004-08-03.
Object id is 5735, canonical name is AutomaticGroup.
Accessed 3044 times total.

Classification:
AMS MSC: 20F10 (Group theory and generalizations :: Special aspects of infinite or finite groups :: Word problems, other decision problems, connections with logic and automata)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)