Grupo automático

En matemáticas , un grupo automático es un grupo finitamente generado equipado con varios autómatas de estados finitos . Estos autómatas representan el gráfico de Cayley del grupo. Es decir, pueden determinar si una representación dada en palabras de un elemento del grupo está en una "forma canónica" y pueden determinar si dos elementos dados en palabras canónicas difieren mediante 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 aceptor de palabras , que acepta para cada elemento de G al menos una palabra para representarlo; ${\displaystyle A^{\ast }}$
• multiplicadores , uno para cada , que aceptan un par ( w ₁ ,  w ₂ ), para las palabras w _i aceptadas por el aceptor de palabras, precisamente cuando están en G . ${\displaystyle a\in A\cup \{1\}}$ ${\displaystyle w_{1}a=w_{2}}$

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

Propiedades

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

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

Ejemplos de grupos automáticos

Los grupos automáticos incluyen:

• Grupos finitos . Para comprobarlo, supongamos que el lenguaje regular es el conjunto de todas las palabras del grupo finito.
• Grupos euclidianos
• Todos los grupos de Coxeter generados finitamente ^[6]
• Grupos geométricamente finitos

Ejemplos de grupos no automáticos

• Grupos Baumslag-Solitar
• Grupos nilpotentes no euclidianos

Grupos biautomáticos

Un grupo es biautomático si tiene dos autómatas multiplicadores, para la multiplicación por la izquierda y por la derecha de elementos del grupo generador, respectivamente. Un grupo biautomático es claramente automático. ^[7]

Algunos ejemplos incluyen:

• Grupos hiperbólicos . ^[8]
• Cualquier grupo Artin de tipo finito , incluidos los grupos trenzados . ^[8]

Estructuras automáticas

La idea de describir estructuras algebraicas con autómatas finitos se puede generalizar desde grupos a otras estructuras. ^[9] Por ejemplo, se generaliza naturalmente a semigrupos automáticos . ^[10]

Referencias

1. Epstein, David BA ; Cannon, James W .; Holt, Derek F.; Levy, Silvio VF; Paterson, Michael S .; Thurston, William P. (1992), Procesamiento de textos en grupos , Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0.
2. Epstein et al. (1992), Sección 2.3, "Grupos automáticos: definición", págs. 45-51.
3. Epstein et al. (1992), Sección 2.4, "Invariancia bajo cambio de generadores", págs. 52-55.
4. Epstein y col. (1992), Teorema 2.3.10, pág. 50.
5. Campbell, Colin M.; Robertson, Edmund F.; Ruskuc, Nik; Thomas, Richard M. (2001), "Semigrupos automáticos" (PDF) , Theoretical Computer Science , 250 (1–2): 365–391, doi : 10.1016/S0304-3975(99)00151-6
6. Brink y Howlett (1993), "Una propiedad de finitud y una estructura automática para grupos de Coxeter", Mathematische Annalen , 296 , Springer Berlin / Heidelberg: 179–190, doi :10.1007/bf01445101, ISSN  0025-5831, S2CID  122177473.
7. Birget, Jean-Camille (2000), Problemas algorítmicos en grupos y semigrupos , Tendencias en matemáticas, Birkhäuser, p. 82, ISBN 0-8176-4130-0
8. Charney, Ruth (1992), "Los grupos de Artin de tipo finito son biautomáticos", Mathematische Annalen , 292 : 671–683, doi :10.1007/BF01444642, S2CID  120654588
9. Khoussainov, Bakhadyr; Rubin, Sasha (2002), Algunas reflexiones sobre las estructuras automáticas , CiteSeerX 10.1.1.7.3913 
10. Epstein et al. (1992), Sección 6.1, "Semigrupos y axiomas especializados", págs. 114-116.

Lectura adicional

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