stringtranslate.com

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]

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]

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).

Ejemplos de grupos automáticos

Los grupos automáticos incluyen:

Ejemplos de grupos no automáticos

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:

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. ^ ab 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