Problema de palavras para grupos - Word problem for groups

Em matemática , especialmente na área de álgebra abstrata conhecida como teoria dos grupos combinatórios , o problema de palavras para um grupo G finitamente gerado é o problema algorítmico de decidir se duas palavras nos geradores representam o mesmo elemento. Mais precisamente, se A é um conjunto finito de geradores para G, então o problema da palavra é o problema de pertinência para a linguagem formal de todas as palavras em A e um conjunto formal de inversos que mapeiam para a identidade sob o mapa natural do monóide livre com involução em um para o grupo G . Se B é um outro grupo gerador finito para G , então a palavra problema sobre o conjunto gerador de B é equivalente à palavra problema sobre o conjunto gerador Uma . Assim, pode-se falar sem ambigüidade da decidibilidade da palavra problema para o grupo G finitamente gerado .

O problema de palavras uniformes relacionadas, mas diferentes, para uma classe K de grupos apresentados recursivamente é o problema algorítmico de decidir, dada como entrada uma apresentação P para um grupo G na classe K e duas palavras nos geradores de G , se as palavras representam o mesmo elemento de L . Alguns autores exigem que a classe K seja definível por um conjunto recursivamente enumerável de apresentações.

História

Ao longo da história do assunto, cálculos em grupos foram realizados usando várias formas normais . Geralmente, isso resolve implicitamente o problema da palavra para os grupos em questão. Em 1911, Max Dehn propôs que o problema da palavra era uma área importante de estudo por si só, junto com o problema de conjugação e o problema de isomorfismo de grupo . Em 1912, ele deu um algoritmo que resolve o problema da palavra e da conjugação para os grupos fundamentais de variedades bidimensionais orientáveis ​​fechadas de gênero maior ou igual a 2. Os autores subsequentes ampliaram muito o algoritmo de Dehn e o aplicaram a uma ampla gama de grupos problemas de decisão teórica .

Foi mostrado por Pyotr Novikov em 1955 que existe um grupo G finitamente apresentado , de forma que a palavra problema para G é indecidível . Segue-se imediatamente que o problema da palavra uniforme também é indecidível. Uma prova diferente foi obtida por William Boone em 1958.

A palavra problema foi um dos primeiros exemplos de um problema insolúvel encontrado não na lógica matemática ou na teoria dos algoritmos , mas em um dos ramos centrais da matemática clássica, a álgebra . Como resultado de sua insolvência, vários outros problemas na teoria dos grupos combinatórios também se mostraram insolúveis.

É importante perceber que a palavra problema está no fato de ser resolvidos para muitos grupos G . Por exemplo, grupos policíclicos têm problemas de palavras solucionáveis, uma vez que a forma normal de uma palavra arbitrária em uma apresentação policíclica é prontamente computável; outros algoritmos para grupos podem, em circunstâncias adequadas, também resolver o problema da palavra, consulte o algoritmo de Todd-Coxeter e o algoritmo de conclusão de Knuth-Bendix . Por outro lado, o fato de que um algoritmo particular não resolve o problema de palavras para um grupo particular não mostra que o grupo tem um problema de palavras insolúvel. Por exemplo, o algoritmo de Dehn não resolve o problema da palavra para o grupo fundamental do toro . No entanto, esse grupo é o produto direto de dois grupos cíclicos infinitos e, portanto, tem um problema de palavra solucionável.

Uma descrição mais concreta

Em termos mais concretos, o problema da palavra uniforme pode ser expresso como uma questão de reescrita , para strings literais . Para uma apresentação P de um grupo G , P irá especificar um certo número de geradores

x , y , z , ...

para L . Precisamos introduzir uma letra para x e outra (por conveniência) para o elemento do grupo representado por x ⁻¹ . Chame essas letras (o dobro dos geradores) de alfabeto para nosso problema. Então, cada elemento em G é representado de alguma forma por um produto ${\ displaystyle \ Sigma}$

abc ... pqr

de símbolos a partir , de algum comprimento, multiplicado em L . A cadeia de comprimento 0 ( string nula ) representa o elemento de identidade e de G . O cerne de todo o problema é ser capaz de reconhecer todas as maneiras como e pode ser representado, dadas algumas relações. ${\ displaystyle \ Sigma}$

O efeito das relações em G é fazer várias dessas cadeias representam o mesmo elemento do G . Na verdade, as relações fornecem uma lista de strings que podem ser introduzidas onde quisermos ou canceladas sempre que as vemos, sem alterar o 'valor', ou seja, o elemento do grupo que é o resultado da multiplicação.

Para um exemplo simples, veja a apresentação { a | a ³ }. Escrevendo A para o inverso de um , temos possíveis cordas combinando qualquer número de símbolos a e A . Sempre que vemos aaa , ou aA ou Aa, podemos eliminá-los. Devemos também nos lembrar de eliminar AAA ; isso diz que, uma vez que o cubo de a é o elemento de identidade de G , o cubo do inverso de a também é . Nessas condições, a palavra problema torna-se fácil. Primeiro reduza as strings para a string vazia, a , aa , A ou AA . Em seguida, observe que também podemos multiplicar por aaa , para que possamos converter A em aa e converter AA em a . O resultado é que o problema da palavra, aqui para o grupo cíclico de ordem três, pode ser resolvido.

Este não é, entretanto, o caso típico. Para o exemplo, temos uma forma canônica disponível que reduz qualquer string a uma de comprimento no máximo três, diminuindo o comprimento monotonicamente. Em geral, não é verdade que se possa obter uma forma canônica para os elementos, por meio do cancelamento gradual. Pode-se ter que usar relações para expandir uma string muitas vezes, a fim de eventualmente encontrar um cancelamento que reduza o comprimento.

O resultado é, no pior caso, que a relação entre as cordas que diz que elas são iguais em G é um problema indecidível .

Exemplos

Os grupos a seguir têm um problema de palavra solucionável:

• Grupos automáticos , incluindo:
  • Grupos finitos
  • Grupos curvos negativamente (também conhecidos como hiperbólicos)
  • Grupos euclidianos
  • Grupos Coxeter
  • Grupos de trança
  • Grupos geometricamente finitos
• Grupos livres finitamente gerados
• Grupos abelianos livres finitamente gerados
• Grupos policíclicos
• Grupos finitamente gerados recursivamente de forma absoluta , incluindo:
  • Grupos simples finitamente apresentados.
• Finita apresentada residualmente finitos grupos
• Um grupo relator (este é um teorema de Magnus), incluindo:
  • Grupos fundamentais de variedades bidimensionais orientáveis ​​fechadas.
• Grupos combináveis
• Grupos autostackable

Exemplos com problemas de palavras insolúveis também são conhecidos:

• Dado um conjunto recursivamente enumerável A de inteiros positivos que tem problema de pertinência insolúvel, ⟨a , b, c, d | um ⁿ ba ⁿ = c ⁿ dc ⁿ  : n ∈ Um ⟩ é um grupo finitos gerado com uma apresentação recursivamente enumeráveis cuja palavra problema é insolúvel
• Cada grupo finitamente gerado com uma apresentação recursivamente enumerável e problema de palavra insolúvel é um subgrupo de um grupo finitamente apresentado com problema de palavra insolúvel
• O número de reladores em um grupo finitamente apresentado com problema de palavra insolúvel pode ser tão baixo quanto 14 ou até 12.
• Um exemplo explícito de uma apresentação curta razoável com problema de palavra insolúvel é dado em Collins 1986:

${\ 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}}}$

Solução parcial do problema da palavra

O problema da palavra para um grupo apresentado recursivamente pode ser parcialmente resolvido no seguinte sentido:

Dada uma apresentação recursiva P = ⟨ X | R ⟩ por um grupo G , definir:

${\ displaystyle S = \ {\ langle u, v \ rangle: u {\ text {e}} v {\ text {são palavras em}} X {\ text {e}} u = v {\ text {in} } G \ \}}$

então há uma função 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 / não para}} \ & {\ text {if}} \ \ langle u, v \ rangle \ notin S \ end {cases}}}$

Mais informalmente, existe um algoritmo que para se u = v , mas não para de outra forma.

Segue-se que para resolver o problema da palavra para P é suficiente construir uma função recursiva g tal que:

${\ displaystyle g (\ langle u, v \ rangle) = {\ begin {cases} 0 & {\ text {if}} \ \ langle u, v \ rangle \ notin S \\ {\ text {indefinido / não para }} \ & {\ text {if}} \ \ langle u, v \ rangle \ in S \ end {cases}}}$

No entanto u = v em L , se e somente se uv ^-1 = 1 em L . Segue-se que para resolver o problema da palavra para P é suficiente construir uma função recursiva h tal que:

${\ displaystyle h (x) = {\ begin {cases} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {indefinido / não para}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {cases}}}$

Exemplo

O seguinte será provado como um exemplo do uso desta técnica:

Teorema: Um grupo residualmente finito finitamente apresentado tem problemas de palavras solucionáveis.

Prova: Suponha que G = ⟨ X | R ⟩ é um grupo finito apresentada, residualmente finito.

Seja S o grupo de todas as permutações de N , os números naturais, que fixa quase todos os números, exceto finitamente:

1. S é localmente finito e contém uma cópia de cada grupo finito.
2. O problema da palavra em S pode ser resolvido calculando-se produtos de permutações.
3. Há uma enumeração recursiva de todos os mapeamentos do finito conjunto X em S .
4. Uma vez que L é residualmente finito, se w é uma palavra na geradores X de L , em seguida, w ≠ 1 em L , se e apenas alguns de mapeamento de X em S induz uma homomorphism tal que w ≠ 1 em S .

Dados esses fatos, algoritmo definido pelo seguinte pseudocódigo:

For every mapping of X into S
    If every relator in R is satisfied in S
        If w ≠ 1 in S
            return 0
        End if
    End if
End for

define uma função recursiva h tal que:

${\ displaystyle h (x) = {\ begin {cases} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {indefinido / não para}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {cases}}}$

Isso mostra que G tem um problema de palavra solucionável.

Insolucionabilidade do problema da palavra uniforme

O critério dado acima, para a resolubilidade da palavra problema em um único grupo, pode ser estendido por um argumento direto. Isso dá o seguinte critério para a resolubilidade uniforme do problema de palavras para uma classe de grupos apresentados finitamente:

Para resolver o problema de palavra uniforme para uma classe K de grupos, é suficiente encontrar uma função recursiva que assume uma apresentação finita P para um grupo G e uma palavra nos geradores de G , tal que sempre 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 {indefinido / não para }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ G \ end {cases}}}$

Teorema de Boone-Rogers: Não existe um algoritmo parcial uniforme que resolva o problema de palavras em todos os grupos apresentados finitamente com problemas de palavras solucionáveis.

Em outras palavras, o problema de palavra uniforme para a classe de todos os grupos apresentados finitamente com problema de palavra solucionável é insolúvel. Isso tem algumas consequências interessantes. Por exemplo, o teorema de incorporação de Higman pode ser usado para construir um grupo contendo uma cópia isomórfica de cada grupo finitamente apresentado com problema de palavras solucionáveis. Parece natural perguntar se este grupo pode ter problemas com palavras solucionáveis. Mas é uma consequência do resultado de Boone-Rogers que:

Corolário: Não existe um grupo universal de problemas de palavras solucionáveis. Ou seja, se G é um grupo finitamente apresentado que contém uma cópia isomórfica de cada grupo finitamente apresentado com problema de palavra resolvível, então o próprio G deve ter problema de palavra insolúvel.

Nota: Suponha que G = ⟨ X | R ⟩ é um grupo finito apresentados com problema palavra solúvel e H é um subconjunto finito de L . Deixe H ^* = ⟨ H ⟩, ser o grupo gerado por H . Em seguida, o problema da palavra em H ^* é solúvel: dadas duas palavras h, k na geradores H de H ^* , escrevê-los como palavras em X e compará-los usando a solução para o problema da palavra em L . É fácil pensar que isso demonstra uma solução uniforme da palavra problema para a classe K (digamos) de grupos finitamente gerados que pode ser incorporado em G . Se fosse esse o caso, a inexistência de um grupo de problemas de palavras solucionáveis ​​universal seguiria facilmente de Boone-Rogers. No entanto, a solução que acabamos de exibir para o problema de palavras para grupos em K não é uniforme. Para ver isto, considere um grupo J = ⟨ Y | T ⟩ ∈ K ; , a fim de utilizar o argumento anterior para resolver o problema da palavra em J , é primeiro necessário para expor um mapeamento e: Y → L que se estende até uma incorporação de e ^* : J → L . Se houvesse uma função recursiva que mapeou (geradas finitamente) apresentações de grupos em K para embeddings em G , então uma solução uniforme para o problema da palavra em K poderia de fato ser construída. Mas não há razão, em geral, para supor que tal função recursiva exista. No entanto, verifica-se que, usando um argumento mais sofisticado, o problema da palavra em J pode ser resolvido sem usando uma incorporação e : J → G . Em vez disso, uma enumeração de homomorphisms é utilizada, e uma vez que tal enumeração pode ser construído de modo uniforme, que resulta em uma solução uniforme para o problema da palavra em K .

Prova de que não existe um grupo universal de problemas de palavras solucionáveis

Suponha que G fosse um grupo de problemas de palavras solucionáveis ​​universal. Dada uma apresentação finito P = ⟨ X | R⟩ de um grupo de H , pode-se recursivamente enumerar todos homomorphisms h : H → G pela primeira enumerar todos os mapeamentos h ^† : X → L . Nem todos estes mapeamentos estender para homomorphisms, mas, uma vez que h ^† ( R ) é finito, é possível distinguir entre homomorphisms e não-homomorphisms, usando a solução para o problema da palavra em L . "Eliminar" não-homomorfismos fornece a enumeração recursiva necessária: h ₁ , h ₂ , ..., h _n , ....

Se H tem um problema de palavra solucionável, então pelo menos um desses homomorfismos deve ser um embedding. Então, dada uma palavra w nos geradores de H :

${\ displaystyle {\ text {If}} \ w \ neq 1 \ {\ text {in}} \ H, \ h_ {n} (w) \ neq 1 \ {\ text {in}} \ G \ {\ texto {para alguns}} \ h_ {n}}$

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

Considere o algoritmo descrito pelo pseudocódigo:

Let n = 0
    Let repeatable = TRUE
        while (repeatable)
            increase n by 1
            if (solution to word problem in G reveals hn(w) ≠ 1 in G)
                Let repeatable = FALSE
output 0.

Isso descreve uma função 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}}}$

A função f depende claramente a apresentação P . Considerando que é uma função das duas variáveis, foi construída uma função recursiva que assume uma apresentação finita P para um grupo H e uma palavra w nos geradores de um grupo G , de modo que sempre que G tem problema de palavra solúvel: ${\ displaystyle f (P, w)}$

${\ displaystyle f (P, w) = {\ begin {cases} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ H \\ {\ text {indefinido / não para }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ H. \ end {cases}}}$

Mas isso resolve uniformemente o problema de palavras para a classe de todos os grupos apresentados finitamente com problemas de palavras solucionáveis, contradizendo Boone-Rogers. Essa contradição prova que G não pode existir.

Estrutura algébrica e o problema da palavra

Existem vários resultados que relacionam a capacidade de resolução do problema da palavra e a estrutura algébrica. O mais significativo deles é o teorema de Boone-Higman :

Um grupo finitamente apresentado tem problemas de palavras solucionáveis ​​se, e somente se, puder ser incorporado em um grupo simples, que pode ser incorporado em um grupo finitamente apresentado.

É amplamente aceito que deve ser possível fazer a construção de forma que o próprio grupo simples seja finitamente apresentado. Nesse caso, seria de se esperar que fosse difícil provar, pois o mapeamento de apresentações para grupos simples teria que ser não recursivo.

O seguinte foi provado por Bernhard Neumann e Angus Macintyre :

Um grupo finitamente apresentado tem problemas de palavras solucionáveis ​​se e somente se puderem ser embutidos em cada grupo algebraicamente fechado

O que é notável sobre isso é que os grupos algebraicamente fechados são tão selvagens que nenhum deles tem uma apresentação recursiva.

O resultado mais antigo relacionando a estrutura algébrica com a capacidade de resolução do problema da palavra é o teorema de Kuznetsov:

Um grupo S simples apresentado recursivamente tem um problema de palavra solucionável.

Para provar isso vamos ⟨ X | R ⟩ ser uma apresentação recursivo para S . Escolha um ∈ S tal que a ≠ 1 em S .

Se w é uma palavra nos geradores X de S , então deixe:

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

Existe uma função 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 {indefinido / não para}} \ & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ S_ {w}. \ End {cases }}}$

Escrever:

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

Então, como a construção de f era uniforme, essa é uma função recursiva de duas variáveis.

Conclui-se que: é recursivo. Por construção: ${\ displaystyle h (w) = g (w, a)}$

${\ displaystyle h (w) = {\ begin {cases} 0 & {\ text {if}} \ a = 1 \ {\ text {in}} \ S_ {w} \\ {\ text {indefinido / não para }} \ & {\ text {if}} \ a \ neq 1 \ {\ text {in}} \ S_ {w}. \ end {cases}}}$

Como S é um grupo simples, seus únicos grupos de quocientes são ele mesmo e o grupo trivial. Desde a ≠ 1 em S , vemos um = 1 em S _w se e somente se S _w é trivial se e somente se w ≠ 1 em S . Portanto:

${\ 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}}}$

A existência de uma tal função de uma seja suficiente para comprovar a palavra problema pode ser resolvido por S .

Esta prova não prova a existência de um algoritmo uniforme para resolver o problema de palavras para esta classe de grupos. A não uniformidade reside na escolha de um elemento não trivial do grupo simples. Não há razão para supor que haja uma função recursiva que mapeia uma apresentação de um grupo simples para um elemento não trivial do grupo. No entanto, no caso de um grupo finitamente apresentado, sabemos que nem todos os geradores podem ser triviais (qualquer gerador individual poderia ser, é claro). Usando este fato é possível modificar a prova para mostrar:

O problema da palavra pode ser resolvido uniformemente para a classe de grupos simples apresentados finitamente.

Veja também

• Combinatória de palavras
• SQ-grupo universal
• Problema de palavra (matemática)
• Problema de acessibilidade
• Autômatos de pilha aninhados (têm sido usados ​​para resolver o problema de palavras para grupos)

Notas

Referências

• WW Boone, FB Cannonito e RC Lyndon . Word Problems: Decision Problem in Group Theory. Holanda: Holanda do Norte. 1973.
• Boone, WW; Higman, G. (1974). “Uma caracterização algébrica da resolubilidade do problema da palavra” . J. Austral. Matemática. Soc . 18 : 41–53. doi : 10.1017 / s1446788700019108 .
• Boone, WW; Rogers Jr, H. (1966). "Sobre um problema de JHC Whitehead e um problema da Igreja de Alonzo" . Matemática. Scand . 19 : 185–192. doi : 10.7146 / math.scand.a-10808 .
• Borisov, VV (1969), "Exemplos simples de grupos com problema de palavra insolúvel", Akademiya Nauk SSSR. Matematicheskie Zametki , 6 : 521–532, ISSN  0025-567X , MR  0260851
• Collins, Donald J. (1969), "problemas de palavras e conjugação em grupos com apenas algumas relações de definição", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 (20-22): 305-324, doi : 10.1002 / malq. 19690152001 , MR  0263903
• Collins, Donald J. (1972), "On a group embedding teoreem of VV Borisov", Bulletin of the London Mathematical Society , 4 (2): 145-147, doi : 10.1112 / blms / 4.2.145 , ISSN  0024-6093 , MR  0314998
• Collins, Donald J. (1986), "A simple presentation of a group with insolvable word problem", Illinois Journal of Mathematics , 30 (2): 230-234, doi : 10.1215 / ijm / 1256044631 , ISSN  0019-2082 , MR  0840121
• Collins, Donald J .; Zieschang, H. (1990), Combinatorial group theory and fundamental groups , Berlin, New York: Springer-Verlag , p. 166, MR  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
• AV Kuznetsov, "Algoritmos como operações em sistemas algébricos", Izvestia Akad. Nauk SSSR Ser Mat (1958)
• CF Miller. "Problemas de decisão para grupos - pesquisa e reflexões." Em Algorithms and Classification in Combinatorial Group Theory , páginas 1–60. Springer, 1991.
• Rotman, Joseph (1994), Uma introdução à teoria dos grupos , Berlim, Nova York: Springer-Verlag , ISBN 978-0-387-94285-8
• Stillwell, J. (1982). “O problema da palavra e o problema do isomorfismo para grupos” . Boletim da AMS . 6 : 33–56. doi : 10.1090 / s0273-0979-1982-14963-1 .
• Nyberg-Brodda, Carl-Fredrik (2021), "O problema da palavra para monoides de uma relação: uma pesquisa", Semigroup Forum , 103 (2): 297-355, arXiv : 2105.02853 , doi : 10.1007 / s00233-021-10216 -8