Problema verbal para grupos

Problema en la teoría de grupos finitos.

En matemáticas , especialmente en el área del álgebra abstracta conocida como teoría combinatoria de grupos , el problema verbal para un grupo G generado finitamente es el problema algorítmico de decidir si dos palabras en los generadores representan el mismo elemento. Más precisamente, si A es un conjunto finito de generadores de G , entonces el problema verbal es el problema de membresía para el lenguaje formal de todas las palabras en A y un conjunto formal de inversos que se corresponden con la identidad bajo el mapa natural del monoide libre con involución de A al grupo G . Si B es otro conjunto generador finito para G , entonces el problema verbal sobre el conjunto generador B es equivalente al problema verbal sobre el conjunto generador A. Por tanto, se puede hablar sin ambigüedades de la decidibilidad del problema verbal para el grupo G finitamente generado .

El problema verbal uniforme relacionado pero diferente para una clase K de grupos presentados recursivamente es el problema algorítmico de decidir, dada como entrada una presentación P para un grupo G en la clase K y dos palabras en los generadores de G , si las palabras representan el mismo elemento de G . Algunos autores exigen que la clase K sea definible mediante un conjunto de presentaciones recursivamente enumerables .

Historia

A lo largo de la historia de la materia, los cálculos en grupos se han realizado utilizando diversas formas normales . Por lo general, estos resuelven implícitamente el problema planteado para los grupos en cuestión. En 1911, Max Dehn propuso que el problema verbal era un área importante de estudio por derecho propio, ^[1] junto con el problema de conjugación y el problema de isomorfismo de grupo . En 1912, presentó un algoritmo que resuelve tanto el problema de palabras como el de conjugación para los grupos fundamentales de variedades bidimensionales cerradas orientables de género mayor o igual a 2. ^[2] Autores posteriores ampliaron enormemente el algoritmo de Dehn y lo aplicaron a una amplia gama de aplicaciones. Gama de problemas de decisión teórica de grupos . ^{[3] [4] [5]}

Pyotr Novikov demostró en 1955 que existe un grupo G presentado finitamente tal que el problema verbal para G es indecidible . ^[6] De ello se deduce inmediatamente que el problema verbal uniforme también es indecidible. William Boone obtuvo una prueba diferente en 1958. ^[7]

El problema verbal fue uno de los primeros ejemplos de un problema irresoluble que no se encuentra en la lógica matemática o la teoría de algoritmos , sino en una de las ramas centrales de las matemáticas clásicas, el álgebra . Como resultado de su insolubilidad, se ha demostrado que varios otros problemas en la teoría combinatoria de grupos también son irresolubles.

Es importante darse cuenta de que, de hecho, el problema planteado tiene solución para muchos grupos G. Por ejemplo, los grupos policíclicos tienen problemas escritos que se pueden resolver, ya que la forma normal de una palabra arbitraria en una presentación policíclica es fácilmente computable; Otros algoritmos para grupos pueden, en circunstancias adecuadas, también resolver el problema verbal; consulte el algoritmo de Todd-Coxeter ^[8] y el algoritmo de finalización de Knuth-Bendix . ^[9] Por otro lado, el hecho de que un algoritmo particular no resuelva el problema verbal para un grupo particular no muestra que el grupo tenga un problema verbal irresoluble. Por ejemplo, el algoritmo de Dehn no resuelve el problema verbal del grupo fundamental del toroide . Sin embargo, este grupo es el producto directo de dos grupos cíclicos infinitos y, por lo tanto, tiene un problema verbal que se puede resolver.

Una descripción más concreta

En términos más concretos, el problema verbal uniforme se puede expresar como una pregunta de reescritura , para cadenas literales . ^[10] Para una presentación P de un grupo G , P especificará un cierto número de generadores

x , y , z , ...

para G. _ Necesitamos introducir una letra para x y otra (por conveniencia) para el elemento del grupo representado por x ⁻¹ . Llame a estas letras (el doble que los generadores) el alfabeto de nuestro problema. Entonces cada elemento en G está representado de alguna manera por un producto ${\displaystyle \Sigma }$

abc... pqr

de símbolos de , de cierta longitud, multiplicados en G . La cadena de longitud 0 ( cadena nula ) representa el elemento de identidad e de G. El quid de todo el problema es poder reconocer todas las formas en que e puede representarse, dadas algunas relaciones. ${\displaystyle \Sigma }$

El efecto de las relaciones en G es hacer que varias de estas cadenas representen el mismo elemento de G. De hecho, las relaciones proporcionan una lista de cadenas que pueden introducirse donde queramos o cancelar cuando las veamos, sin cambiar el 'valor', es decir, el elemento del grupo que es el resultado de la multiplicación.

Para ver un ejemplo sencillo, tomemos la presentación { a | un ³ }. Escribiendo A para la inversa de a , tenemos posibles cadenas que combinan cualquier número de símbolos a y A . Siempre que veamos aaa , o aA o Aa, podemos tacharlos. También debemos recordar eliminar a AAA ; esto dice que dado que el cubo de a es el elemento identidad de G , también lo es el cubo de la inversa de a . En estas condiciones, el problema planteado resulta fácil. Primero reduzca las cadenas a la cadena vacía, a , aa , A o AA . Luego tenga en cuenta que también podemos multiplicar por aaa , por lo que podemos convertir A en aa y convertir AA en a . El resultado es que el problema verbal, aquí para el grupo cíclico de orden tres, tiene solución.

Sin embargo, éste no es el caso típico. Por ejemplo, tenemos una forma canónica disponible que reduce cualquier cadena a una de longitud como máximo tres, disminuyendo la longitud de forma monótona. En general, no es cierto que se pueda obtener una forma canónica para los elementos mediante cancelación gradual. Es posible que tengamos que usar relaciones para expandir una cadena muchas veces, con el fin de encontrar eventualmente una cancelación que reduzca la longitud.

El resultado es, en el peor de los casos, que la relación entre cadenas que dice que son iguales en G es un problema indecidible .

Ejemplos

Los siguientes grupos tienen un problema verbal que se puede resolver:

• Grupos automáticos , que incluyen:
  • grupos finitos
  • Grupos curvados negativamente (también conocidos como hiperbólicos)
  • Grupos euclidianos
  • Grupos de coxeter
  • Grupos de trenzas
  • Grupos geométricamente finitos
• Grupos libres finitamente generados
• Grupos abelianos libres finitamente generados
• Grupos policíclicos
• Grupos presentados de forma recursiva y generada finitamente , ^[11] que incluyen:
  • Grupos simples presentados finitamente.
• Grupos residualmente finitos presentados finitamente
• Un grupo de relatores ^[12] (este es un teorema de Magnus), que incluye:
  • Grupos fundamentales de variedades bidimensionales cerradas orientables.
• Grupos combinables
• Grupos autoapilables

También se conocen ejemplos con problemas planteados sin solución:

• Dado un conjunto recursivamente enumerable A de enteros positivos que tiene un problema de membresía insoluble, ⟨ a,b,c,d | a ⁿ ba ⁿ = c ⁿ dc ⁿ  : n ∈ A ⟩ es un grupo generado finitamente con una presentación recursivamente enumerable cuyo problema verbal es insoluble ^[13]
• Cada grupo finitamente generado con una presentación recursivamente enumerable y un problema verbal insoluble es un subgrupo de un grupo presentado finitamente con un problema verbal insoluble ^[14]
• El número de relatores en un grupo presentado de forma finita con un problema verbal insoluble puede ser tan bajo como 14 ^[15] o incluso 12. ^{[16] [17]}
• Un ejemplo explícito de una presentación breve razonable con un problema planteado insoluble se da en Collins 1986: ^{[18] [19]}

${\displaystyle {\begin{array}{lllll}\langle &a,b,c,d,e,p,q,r,t,k&|&&\\&p^{10}a=ap,&pacqr=rpcaq,&ra=ar,&\\&p^{10}b=bp,&p^{2}adq^{2}r=rp^{2}daq^{2},&rb=br,&\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},&rc=cr,&\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},&rd=dr,&\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},&re=er,&\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},&pt=tp,&\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},&qt=tq,&\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},&&\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},&&\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}&&\rangle \end{array}}}$

Solución parcial del problema verbal.

El problema verbal para un grupo presentado recursivamente se puede resolver parcialmente en el siguiente sentido:

Dada una presentación recursiva P = ⟨ X | R ⟩ para un grupo G , defina:

${\displaystyle S=\{\langle u,v\rangle :u{\text{ and }}v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}}$

entonces existe una función recursiva parcial f _P tal que:

${\displaystyle f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}}$

De manera más informal, existe un algoritmo que se detiene si u = v , pero no lo hace en caso contrario.

De ello se deduce que para resolver el problema planteado para P es suficiente construir una función recursiva g tal que:

${\displaystyle g(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}}$

Sin embargo u = v en G si y sólo si uv ⁻¹ =1 en G . De ello se deduce que para resolver el problema planteado para P es suficiente construir una función recursiva h tal que:

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Ejemplo

Como ejemplo del uso de esta técnica se demostrará lo siguiente:

Teorema: Un grupo residualmente finito presentado finitamente tiene un problema verbal que se puede resolver.

Prueba: Supongamos G = ⟨ X | R ⟩ es un grupo residualmente finito y presentado de forma finita.

Sea S el grupo de todas las permutaciones de N , los números naturales, que fijan todos los números excepto un número finito, entonces:

1. S es localmente finito y contiene una copia de cada grupo finito.
2. El problema verbal en S se puede resolver calculando productos de permutaciones.
3. Hay una enumeración recursiva de todas las asignaciones del conjunto finito X en S.
4. Dado que G es residualmente finito, si w es una palabra en los generadores X de G , entonces w ≠ 1 en G si y solo de alguna aplicación de X en S induce un homomorfismo tal que w ≠ 1 en S.

Teniendo en cuenta estos hechos, algoritmo definido por el siguiente pseudocódigo:

Para cada mapeo de X en S Si cada relación en R se satisface en S Si w ≠ 1 en S devuelve 0 Fin si  Fin si Fin para

define una función recursiva h tal que:

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Esto muestra que G tiene un problema verbal que se puede resolver.

Insolubilidad del problema verbal uniforme

El criterio dado anteriormente, para la solucion del problema planteado en un solo grupo, puede ampliarse mediante un argumento sencillo. Esto da el siguiente criterio para la solucion uniforme del problema verbal para una clase de grupos presentados finitamente:

Para resolver el problema verbal uniforme para una clase K de grupos, es suficiente encontrar una función recursiva que tome una presentación finita P para un grupo G y una palabra en los generadores de G , tal que siempre que G ∈ K : ${\displaystyle f(P,w)}$ ${\displaystyle w}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}}$

Teorema de Boone-Rogers: No existe un algoritmo parcial uniforme que resuelva el problema verbal en todos los grupos presentados finitamente con problemas verbales resolubles.

En otras palabras, el problema verbal uniforme para la clase de todos los grupos presentados finitamente con un problema verbal resoluble no tiene solución. Esto tiene algunas consecuencias interesantes. Por ejemplo, el teorema de incrustación de Higman se puede utilizar para construir un grupo que contenga una copia isomorfa de cada grupo presentado finitamente con un problema verbal que se pueda resolver. Parece natural preguntar si este grupo puede tener problemas planteados que puedan resolverse. Pero es una consecuencia del resultado de Boone-Rogers que:

Corolario: No existe un grupo universal de problemas verbales que se pueda resolver. Es decir, si G es un grupo presentado finitamente que contiene una copia isomorfa de cada grupo presentado finitamente con un problema verbal que se puede resolver, entonces el propio G debe tener un problema verbal que no se puede resolver.

Observación: Supongamos que G = ⟨ X | R ⟩ es un grupo presentado finitamente con un problema verbal que se puede resolver y H es un subconjunto finito de G . Sea H ^* = ⟨ H ⟩, el grupo generado por H . Entonces, el problema verbal en H ^* tiene solución: dadas dos palabras h, k en los generadores H de H ^* , escríbalas como palabras en X y compárelas usando la solución al problema verbal en G. Es fácil pensar que esto demuestra una solución uniforme del problema verbal para la clase K (digamos) de grupos generados finitamente que pueden incluirse en G. Si este fuera el caso, la inexistencia de un grupo universal de problemas verbales con solución se derivaría fácilmente de Boone-Rogers. Sin embargo, la solución que se acaba de exponer para el problema planteado para grupos en K no es uniforme. Para ver esto, considere un grupo J = ⟨ Y | T ⟩ ∈ K ; Para utilizar el argumento anterior para resolver el problema verbal en J , primero es necesario exhibir una aplicación e: Y → G que se extienda a una incrustación e ^* : J → G. Si hubiera una función recursiva que mapeara (generadas finitamente) presentaciones de grupos en K con incrustaciones en G , entonces se podría construir una solución uniforme del problema verbal en K. Pero, en general, no hay razón para suponer que exista tal función recursiva. Sin embargo, resulta que, usando un argumento más sofisticado, el problema verbal en J se puede resolver sin usar una incrustación e : J → G . En su lugar, se utiliza una enumeración de homomorfismos y, dado que dicha enumeración se puede construir de manera uniforme, da como resultado una solución uniforme al problema verbal en K.

Prueba de que no existe un grupo universal de problemas verbales que se pueda resolver

Supongamos que G fuera un grupo universal de problemas verbales con solución. Dada una presentación finita P = ⟨ X | R⟩ de un grupo H , se pueden enumerar recursivamente todos los homomorfismos h : H → G enumerando primero todas las asignaciones h ^† : X → G. No todas estas asignaciones se extienden a homomorfismos, pero, dado que h ^† ( R ) es finito, es posible distinguir entre homomorfismos y no homomorfismos utilizando la solución del problema verbal en G . "Eliminar" los no homomorfismos proporciona la enumeración recursiva requerida: h ₁ , h ₂ , ..., h _n , ... .

Si H tiene un problema verbal que se puede resolver, entonces al menos uno de estos homomorfismos debe ser una incrustación. Entonces, dada una palabra w en los generadores de H :

${\displaystyle {\text{If}}\ w\neq 1\ {\text{in}}\ H,\ h_{n}(w)\neq 1\ {\text{in}}\ G\ {\text{for some}}\ h_{n}}$

${\displaystyle {\text{If}}\ w=1\ {\text{in}}\ H,\ h_{n}(w)=1\ {\text{in}}\ G\ {\text{for all}}\ h_{n}}$

Considere el algoritmo descrito por el pseudocódigo:

Sea  n = 0 Sea  repetible = VERDADERO mientras ( repetible ) aumentar n en 1 si (la solución al problema escrito en G revela h n ( w ) ≠ 1 en G ) Sea  repetible = FALSOsalida 0.

Esto describe una función recursiva:

${\displaystyle f(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

La función f depende claramente de la presentación P . Considerando que es una función de las dos variables, se ha construido una función recursiva que toma una presentación finita P para un grupo H y una palabra w en los generadores de un grupo G , de modo que siempre que G tenga un problema verbal soluble: ${\displaystyle f(P,w)}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

Pero esto resuelve uniformemente el problema verbal para la clase de todos los grupos presentados finitamente con problemas verbales resolubles, contradiciendo a Boone-Rogers. Esta contradicción demuestra que G no puede existir.

Estructura algebraica y el problema verbal.

Hay una serie de resultados que relacionan la solucion del problema planteado y la estructura algebraica. El más significativo de ellos es el teorema de Boone-Higman:

Un grupo presentado finitamente tiene un problema verbal resoluble si y sólo si puede integrarse en un grupo simple que pueda integrarse en un grupo presentado finitamente.

Se cree ampliamente que debería ser posible realizar la construcción de manera que el grupo simple en sí se presente de forma finita. De ser así, se esperaría que fuera difícil demostrarlo, ya que el mapeo de presentaciones a grupos simples tendría que ser no recursivo.

Bernhard Neumann y Angus Macintyre han demostrado lo siguiente :

Un grupo presentado finitamente tiene un problema verbal que se puede resolver si y sólo si puede incluirse en todo grupo algebraicamente cerrado.

Lo notable de esto es que los grupos algebraicamente cerrados son tan salvajes que ninguno de ellos tiene una presentación recursiva.

El resultado más antiguo que relaciona la estructura algebraica con la solucion del problema verbal es el teorema de Kuznetsov:

Un grupo S simple presentado recursivamente tiene un problema verbal que se puede resolver.

Para probar esto, sea ⟨ X | R ⟩ sea una presentación recursiva para S . Elija a ∈ S tal que a ≠ 1 en S .

Si w es una palabra en los generadores X de S , entonces sea:

${\displaystyle S_{w}=\langle X|R\cup \{w\}\rangle .}$

Existe una función recursiva tal que: ${\displaystyle f_{\langle X|R\cup \{w\}\rangle }}$

${\displaystyle f_{\langle X|R\cup \{w\}\rangle }(x)={\begin{cases}0&{\text{if}}\ x=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Escribir:

${\displaystyle g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).}$

Entonces, debido a que la construcción de f fue uniforme, ésta es una función recursiva de dos variables.

De ello se deduce que: es recursivo. Por construcción: ${\displaystyle h(w)=g(w,a)}$

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ a\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Dado que S es un grupo simple, sus únicos grupos cocientes son él mismo y el grupo trivial. Dado que a ≠ 1 en S , vemos a = 1 en S _w si y solo si S _w es trivial si y solo si w ≠ 1 en S . Por lo tanto:

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ S\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{cases}}}$

La existencia de tal función es suficiente para demostrar que el problema verbal tiene solución para S.

Esta prueba no prueba la existencia de un algoritmo uniforme para resolver el problema verbal para esta clase de grupos. La no uniformidad reside en elegir un elemento no trivial del grupo simple. No hay razón para suponer que exista una función recursiva que asigne una presentación de grupos simples a un elemento no trivial del grupo. Sin embargo, en el caso de un grupo presentado finitamente sabemos que no todos los generadores pueden ser triviales (cualquier generador individual podría serlo, por supuesto). Usando este hecho es posible modificar la prueba para mostrar:

El problema planteado tiene solución uniforme para la clase de grupos simples presentados finitamente.

Ver también

• Combinatoria de palabras
• grupo SQ-universal
• Problema verbal (matemáticas)
• Problema de accesibilidad
• Autómatas de pila anidados (se han utilizado para resolver problemas verbales para grupos)

Notas

1. Dehn 1911.
2. Dehn 1912.
3. Greendlinger, Martin (junio de 1959), "Algoritmo de Dehn para el problema verbal", Communications on Pure and Applied Mathematics , 13 (1): 67–83, doi :10.1002/cpa.3160130108.
4. Lyndon, Roger C. (septiembre de 1966), "Sobre el algoritmo de Dehn", Mathematische Annalen , 166 (3): 208–228, doi :10.1007/BF01361168, hdl : 2027.42/46211 , S2CID  36469569.
5. Schupp, Paul E. (junio de 1968), "Sobre el algoritmo de Dehn y el problema de la conjugación", Mathematische Annalen , 178 (2): 119–130, doi :10.1007/BF01350654, S2CID  120429853.
6. Novikov, PS (1955), "Sobre la insolubilidad algorítmica del problema verbal en teoría de grupos", Actas del Instituto Steklov de Matemáticas (en ruso), 44 : 1–143, Zbl  0068.01301
7. Boone, William W. (1958), "El problema verbal" (PDF) , Actas de la Academia Nacional de Ciencias , 44 (10): 1061–1065, Bibcode : 1958PNAS...44.1061B, doi : 10.1073/pnas .44.10.1061 , PMC 528693 , PMID  16590307, ​​Zbl  0086.24701 
8. Todd, J.; Coxeter, HSM (1936). "Un método práctico para enumerar clases laterales de un grupo abstracto finito". Actas de la Sociedad Matemática de Edimburgo . 5 (1): 26–34. doi : 10.1017/S0013091500008221 .
9. Knuth, D.; Bendix, P. (2014) [1970]. "Problemas planteados simples en álgebras universales". En Leech, J. (ed.). Problemas computacionales en álgebra abstracta: actas de una conferencia celebrada en Oxford bajo los auspicios del Atlas Computer Laboratory del Science Research Council, del 29 de agosto al 2 de septiembre de 1967 . Saltador. págs. 263–297. ISBN 9781483159423.
10. Rotman 1994.
11. Simmons, H. (1973). "El problema verbal de presentaciones absolutas". J. Matemáticas de Londres. Soc . T2-6 (2): 275–280. doi :10.1112/jlms/s2-6.2.275.
12. Lyndon, Roger C.; Schupp, Paul E (2001). Teoría combinatoria de grupos. Saltador. págs. 1–60. ISBN 9783540411581.
13. Collins y Zieschang 1990, pág. 149.
14. Collins y Zieschang 1993, Cor. 7.2.6. sfn error: no target: CITEREFCollinsZieschang1993 (help)
15. Collins 1969.
16. Borísov 1969.
17. Collins 1972.
18. Collins 1986.
19. Usamos la versión corregida del Catálogo de sistemas algebraicos de John Pedersen.

Referencias

• Boone, WW; Cannonito, FB; Lyndon, Roger C. (1973). Problemas planteados: problemas de decisión y el problema de Burnside en teoría de grupos. Estudios de lógica y fundamentos de las matemáticas. vol. 71. Holanda Septentrional. ISBN 9780720422719.
• Boone, WW; Higman, G. (1974). "Una caracterización algebraica de la solucion del problema verbal". J.Austral. Matemáticas. Soc . 18 : 41–53. doi : 10.1017/s1446788700019108 .
• Boone, WW; Rogers hijo, H. (1966). "Sobre un problema de JHC Whitehead y un problema de Alonzo Church". Matemáticas. Escanear . 19 : 185-192. doi : 10.7146/math.scand.a-10808 .
• Borisov, VV (1969), "Ejemplos simples de grupos con problemas verbales sin solución", Akademiya Nauk SSSR. Matematicheskie Zametki , 6 : 521–532, ISSN  0025-567X, SEÑOR  0260851
• Collins, Donald J. (1969), "Problemas de palabras y conjugación en grupos con sólo unas pocas relaciones definitorias", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 (20–22): 305–324, doi :10.1002/malq. 19690152001, señor  0263903
• Collins, Donald J. (1972), "Sobre un teorema de incrustación de grupos de VV Borisov", Boletín de la Sociedad Matemática de Londres , 4 (2): 145–147, doi :10.1112/blms/4.2.145, ISSN  0024-6093 , señor  0314998
• Collins, Donald J. (1986), "Una presentación simple de un grupo con un problema verbal sin solución", Illinois Journal of Mathematics , 30 (2): 230–234, doi : 10.1215/ijm/1256044631 , ISSN  0019-2082, SEÑOR  0840121
• Collins, Donald J.; Zieschang, H. (1990), Teoría combinatoria de grupos y grupos fundamentales , Springer-Verlag , p. 166, señor  1099152
• Dehn, Max (1911), "Über unendliche diskontinuierliche Gruppen", Mathematische Annalen , 71 (1): 116–144, doi :10.1007/BF01456932, ISSN  0025-5831, MR  1511645, S2CID  123478582
• Dehn, Max (1912), "Transformation der Kurven auf zweiseitigen Flächen", Mathematische Annalen , 72 (3): 413–421, doi :10.1007/BF01456725, ISSN  0025-5831, MR  1511705, S2CID  122988176
• Kuznetsov, AV (1958). "Algoritmos como operaciones en sistemas algebraicos". Izvestia Akád. Nauk SSSR Ser Mat . 13 (3): 81.
• Miller, CF (1991). "Problemas de decisión para grupos: encuesta y reflexiones". Algoritmos y clasificación en teoría combinatoria de grupos . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas. vol. 23. Saltador. págs. 1–60. doi :10.1007/978-1-4613-9730-4_1. ISBN 978-1-4613-9730-4.
• Nyberg-Brodda, Carl-Fredrik (2021), "El problema verbal para monoides de una relación: una encuesta", Semigroup Forum , 103 (2): 297–355, arXiv : 2105.02853 , doi : 10.1007/s00233-021-10216 -8
• Rotman, Joseph (1994), Introducción a la teoría de grupos , Springer-Verlag , ISBN 978-0-387-94285-8
• Stillwell, J. (1982). "El problema verbal y el problema de isomorfismo para grupos". Boletín de la AMS . 6 : 33–56. doi : 10.1090/s0273-0979-1982-14963-1 .