En matemáticas , un grupo automático es un grupo generado finita equipado con varios autómatas de estado finito . Estos autómatas representan el gráfico de Cayley del grupo. Es decir, pueden saber si una representación de palabra dada de un elemento de grupo está en una "forma canónica" y pueden saber si dos elementos dados en palabras canónicas difieren por 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 estado finito: [2]
- el aceptador de palabras , que acepta para cada elemento de G al menos una palabra en representándolo;
- multiplicadores , uno para cada, que aceptan un par ( w 1 , w 2 ), para palabras w i aceptadas por el aceptor de palabras, precisamente cuandoen G .
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 determinada se puede poner en forma canónica en tiempo cuadrático, en función del cual el problema verbal se puede resolver probando si las formas canónicas de dos palabras representan el mismo elemento (usando el multiplicador para). [4]
Los grupos automáticos se caracterizan por la propiedad del compañero de viaje . [5] Deja denotar la distancia entre en el gráfico de Cayley de . Entonces, G es automático con respecto a un aceptador de palabras L si y solo si hay una constante tal que para todas las palabras que difieren como máximo en un generador, la distancia entre los respectivos prefijos de u y v está delimitada por C . En otras palabras, dónde para el k-ésimo prefijo de (o 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 el diámetro C en el gráfico de Cayley).
Ejemplos de grupos automáticos
Los grupos automáticos incluyen:
- Grupos finitos . Para ver esto, tome el lenguaje regular como el conjunto de todas las palabras en el grupo finito.
- Grupos euclidianos
- Todos los grupos Coxeter generados de forma finita [6]
- Grupos geométricamente finitos
Ejemplos de grupos no automáticos
Grupos biautomáticos
Un grupo es biautomático si tiene dos autómatas multiplicadores, para la multiplicación izquierda y derecha por elementos del grupo electrógeno, respectivamente. Un grupo biautomático es claramente automático. [7]
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 de grupos a otras estructuras. [9] Por ejemplo, se generaliza naturalmente a semigrupos automáticos . [10]
Referencias
- ^ 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.
- ^ Epstein y col. (1992) , Sección 2.3, "Grupos automáticos: Definición", págs. 45–51.
- ^ Epstein y col. (1992) , Sección 2.4, "Invarianza bajo cambio de generadores", págs. 52-55.
- ^ Epstein y col. (1992) , Teorema 2.3.10, pág. 50.
- ^ Campbell, Colin M .; Robertson, Edmund F .; Ruskuc, Nik; Thomas, Richard M. (2001), "Automatic semigroups" (PDF) , Theoretical Computer Science , 250 (1–2): 365–391, doi : 10.1016 / S0304-3975 (99) 00151-6
- ^ Brink y Howlett (1993), "Una propiedad de finitud y una estructura automática para grupos Coxeter", Mathematische Annalen , Springer Berlin / Heidelberg, doi : 10.1007 / bf01445101 , ISSN 0025-5831 .
- ^ Birget, Jean-Camille (2000), Problemas algorítmicos en grupos y semigrupos , Tendencias en matemáticas, Birkhäuser, p. 82, ISBN 0-8176-4130-0
- ^ a b Charney, Ruth (1992), "Los grupos de Artin de tipo finito son biautomáticos", Mathematische Annalen , 292 : 671–683, doi : 10.1007 / BF01444642
- ^ Khoussainov, Bakhadyr; Rubin, Sasha (2002), Algunas reflexiones sobre estructuras automáticas , CiteSeerX 10.1.1.7.3913
- ^ Epstein y col. (1992) , Sección 6.1, "Semigroups and Specialized Axioms", págs. 114-116.
Otras lecturas
- Chiswell, Ian (2008), Un curso en lenguajes formales, autómatas y grupos , Springer, ISBN 978-1-84800-939-4.