Grupo automático

En matemáticas , un grupo automático es un grupo finitamente generado dotado de varios autómatas de estados finitos . Estos autómatas representan el grafo de Cayley del grupo. Es decir, pueden determinar si una representación verbal dada de un elemento del grupo está en una "forma canónica" y pueden determinar si dos elementos dados en palabras canónicas difieren en un generador. ^{[ 1 ]}

Más precisamente, sea G un grupo y A un conjunto finito de generadores. Entonces, una estructura automática de G con respecto a A es un conjunto de autómatas de estados finitos: ^{[ 2 ]}

• el aceptador de palabras , que acepta para cada elemento de G al menos una palabra en${\displaystyle A^{\ast }}$representándolo;
• multiplicadores , uno para cada${\displaystyle a\in A\cup \{1\}}$, que aceptan un par ( w ₁ , w ₂ ), para las palabras w _i aceptadas por el receptor de palabras, precisamente cuando ${\displaystyle w_{1}a=w_{2}}$en G.​

La propiedad de ser automático no depende del conjunto de generadores. ^{[ 3 ]}

Los grupos automáticos tienen problemas de palabras que se pueden resolver en tiempo cuadrático. Más aún, una palabra dada se puede convertir a forma canónica en tiempo cuadrático, basándose en lo cual el problema de palabras se puede resolver probando si las formas canónicas de dos palabras representan el mismo elemento (usando el multiplicador para${\displaystyle a=1}$). ^{[ 4 ]}

Los grupos automáticos se caracterizan por la propiedad del compañero de viaje . ^{[ 5 ]} Sea${\displaystyle d(x,y)}$denotan la distancia entre${\displaystyle x,y\in G}$en el gráfico de Cayley de${\displaystyle G}$Entonces, G es automático con respecto a un aceptador de palabras L si y solo si existe una constante${\displaystyle C\in \mathbb {N} }$de tal manera que para todas las palabras${\displaystyle u,v\in L}$que difieren como máximo en un generador, la distancia entre los prefijos respectivos de u y v está limitada por C. En otras palabras,${\displaystyle \forall u,v\in L,d(u,v)\leq 1\Rightarrow \forall k\in \mathbb {N} ,d(u_{|k},v_{|k})\leq C}$dónde${\displaystyle w_{|k}}$para el k-ésimo prefijo de${\displaystyle w}$(o${\displaystyle w}$sí mismo si${\displaystyle k>|w|}$). Esto significa que, al leer las palabras de forma sincrónica, es posible realizar un seguimiento de la diferencia entre ambos elementos con un número finito de estados (el entorno de la identidad con diámetro C en el grafo de Cayley).

Los grupos automáticos incluyen:

• Grupos finitos . Para ver esto, tomemos el lenguaje regular como el conjunto de todas las palabras en el grupo finito.
• grupos euclidianos
• Todos los grupos de Coxeter generados finitamente ^{[ 6 ]}
• grupos geométricamente finitos

• Grupos Baumslag-Solitar
• Grupos nilpotentes no euclidianos
• No todos los grupos CAT(0) son biautomáticos ^{[ 7 ] [ 8 ]}

Un grupo es biautomático si posee dos autómatas multiplicadores, uno para la multiplicación por la izquierda y otro para la multiplicación por la derecha por elementos del conjunto generador. Un grupo biautomático es claramente automático. ^{[ 9 ]}

Algunos ejemplos son:

• Grupos hiperbólicos . ^{[ 10 ]}
• Cualquier grupo de Artin de tipo finito , incluidos los grupos de trenzas . ^{[ 10 ]}

La idea de describir estructuras algebraicas con autómatas finitos puede generalizarse de grupos a otras estructuras. ^{[ 11 ]} Por ejemplo, se generaliza naturalmente a semigrupos automáticos . ^{[ 12 ]}

• Chiswell, Ian (2008), Un curso de lenguajes formales, autómatas y grupos , Springer, ISBN 978-1-84800-939-4.