Szöveges probléma csoportok számára - Word problem for groups

A matematika , különösen a területén absztrakt algebra ismert kombinatorikai csoport elmélet , a szöveges feladat egy végesen generált csoport G az algoritmikus probléma eldöntése két szót generátorok képviseli ugyanazt az elemet. Pontosabban, ha A a G generátorok véges halmaza, akkor a szóprobléma az A összes szavának formális nyelvének tagsági problémája, és az inverzek formális halmaza, amely a szabad monoidból származó természetes térkép alatti identitáshoz társul. involúció az A -n a G csoportba . Ha B egy másik véges generátorhalmaz G számára , akkor a B generáló halmaz fölötti szófeladat egyenértékű az A generáló halmaz szófeladatával . Így egyértelműen beszélhetünk a szófeladat eldönthetőségéről a végesen generált G csoport esetében .

A rekurzívan bemutatott csoportok K osztályának ezzel kapcsolatos, de eltérő egységes szöveges feladata az algoritmikus probléma annak eldöntésére, hogy bemenetként egy P prezentációt adnak a K osztály G csoportjának és két szót a G generátoroknak , hogy a szavak képviselik -e a G ugyanaz az eleme . Egyes szerzők megkövetelik, hogy a K osztály meghatározható legyen egy rekurzívan felsorolható prezentációhalmazzal.

Történelem

A téma története során a csoportokban végzett számításokat különböző normál formák segítségével végezték . Ezek általában implicit módon megoldják a szóban forgó csoportok szöveges feladatát. 1911 -ben Max Dehn azt javasolta, hogy a szöveges probléma önmagában fontos tanulmányozási terület legyen, a konjugációs problémával és a csoport izomorfizmus problémájával együtt . 1912-ben olyan algoritmust adott, amely mind a szó, mind a konjugációs problémát megoldja a zárt, tájolható kétdimenziós nemzetség sokaságainak alapvető csoportjai esetén, amelyek nagyobbak vagy egyenlők. A későbbi szerzők nagymértékben kiterjesztették Dehn algoritmusát, és a csoportok széles körére alkalmazták elméleti döntési problémák .

Ezt mutatja Pjotr Novikov 1955 hogy létezik egy véges bemutatott csoport, G úgy, hogy a szó probléma G jelentése eldönthetetlen . Ebből azonnal következik, hogy az egységes szöveges probléma is eldönthetetlen. Más bizonyítékot kapott William Boone 1958 -ban.

A szöveges feladat volt az egyik első példa egy megoldhatatlan problémára, amely nem a matematikai logikában vagy az algoritmuselméletben , hanem a klasszikus matematika egyik központi ágában, az algebrában található . Megoldhatatlansága következtében a kombinatorikus csoportelmélet számos más problémája is megoldhatatlannak bizonyult.

Fontos felismerni, hogy a szöveges probléma valójában sok G csoport számára megoldható . Például a policiklusos csoportoknak megoldható szöveges feladataik vannak, mivel egy policiklusos prezentációban tetszőleges szó normál formája könnyen kiszámítható; más algoritmusok csoportoknak megfelelő körülmények között szintén megoldhatják a szöveges feladatot, lásd a Todd – Coxeter algoritmust és a Knuth – Bendix befejezési algoritmust . Másrészt az a tény, hogy egy adott algoritmus nem oldja meg a szöveges feladatot egy adott csoport esetében, nem azt mutatja, hogy a csoportnak megoldhatatlan szöveges problémája van. Például Dehn algoritmusa nem oldja meg a szöveges feladatot a tórusz alapvető csoportjában . Ez a csoport azonban két végtelen ciklikus csoport közvetlen terméke, és így megoldható szöveges problémája van.

Egy konkrétabb leírás

Konkrétabban fogalmazva, az egységes szövegprobléma átírási kérdésként fejezhető ki , szó szerinti húrok esetén . Egy bemutató P egy csoport G , P meghatározza egy bizonyos számú generátorok

x , y , z , ...

a G . Be kell vezetnünk az egyik betűt az x -hez , a másikat (a kényelem érdekében) az x ⁻¹ által jelölt csoportelemhez . Nevezze ezeket a betűket (kétszer annyi, mint a generátorok) a problémánk ábécéjének . Ezután minden egyes eleme a G képviselteti magát valamilyen módon , amelyet a termék ${\ displaystyle \ Sigma}$

abc ... pqr

szimbólumok , bizonyos hosszúságúak, G -ben szorozva . A 0 hosszúságú karakterlánc ( null string ) a G e azonosító elemét jelenti . Az egész probléma lényege, hogy felismerjük az e ábrázolásának minden módját , tekintettel bizonyos összefüggésekre. ${\ displaystyle \ Sigma}$

A hatás a kapcsolatok a G az, hogy a különböző ilyen húrok jelentése azonos eleme G . Valójában a relációk listát adnak azokról a karakterláncokról, amelyeket tetszés szerint be lehet vezetni, vagy bármikor törölni lehet, anélkül, hogy látnánk őket, anélkül, hogy megváltoztatnánk az „értéket”, azaz a szorzás eredményeként létrejött csoportelemet.

Egy egyszerű példa kedvéért vegye a { a | a ³ }. Írás egy az inverzét egy , már a lehetséges karakterek kombinálásával tetszőleges számú szimbólum egy és egy . Amikor aaa -t , vagy aA -t vagy Aa -t látunk, ezeket kihagyhatjuk . Emlékeznünk kell arra is, hogy töröljük az AAA -t ; ez azt mondja, hogy mivel a kocka egy az identitás eleme G , így a kocka a fordított egy . Ilyen körülmények között a szöveges probléma egyszerűvé válik. Először csökkentse a karakterláncokat az üres karakterláncra, a , aa , A vagy AA . Akkor vegye figyelembe, hogy is szorozzuk aaa , így tudjuk alakítani egy az aa és konvertálni AA , hogy egy . Az eredmény az, hogy a szóprobléma, itt a harmadik rendű ciklikus csoportra megoldható.

Ez azonban nem a tipikus eset. Például egy kanonikus űrlap áll rendelkezésünkre, amely a karaktersorozatot legfeljebb háromra csökkenti, a hosszúság monoton csökkentésével. Általában nem igaz, hogy az elemekhez kanonikus formát lehet kapni, lépésről lépésre történő törléssel. Lehet, hogy relációkat kell használnia a karakterlánc sokszoros kibontásához, hogy végül találjon olyan törlést, amely lerövidíti a hosszúságot.

A végeredmény, a legrosszabb esetben, hogy az összefüggés húrok, hogy azt mondja, hogy egyenlőek G egy eldönthetetlen probléma .

Példák

A következő csoportoknak van megoldható szöveges problémája:

• Automatikus csoportok , beleértve:
  • Véges csoportok
  • Negatívan ívelt (más néven hiperbolikus) csoportok
  • Euklideszi csoportok
  • Coxeter csoportok
  • Zsinórcsoportok
  • Geometriailag véges csoportok
• Végesen generált ingyenes csoportok
• Végesen generált ingyenes abeli csoportok
• Policiklusos csoportok
• Végesen generált rekurzív abszolút bemutatott csoportok , beleértve:
  • Végesen bemutatott egyszerű csoportok.
• Végesen bemutatott maradékul véges csoportok
• Az egyik relatorcsoport (ez Magnus tétele), többek között:
  • A zárt tájolható kétdimenziós elosztók alapvető csoportjai.
• Kombinálható csoportok
• Automatikusan tömöríthető csoportok

Ismertek példák megoldhatatlan szöveges problémákkal is:

• Adott egy rekurzív felsorolható halmaz A pozitív egészek, amely oldhatatlan tagság probléma ⟨ a, b, c, d | egy ⁿ BA ⁿ = c ⁿ dc ⁿ  : n ∈ A ⟩ egy véges generált csoport egy rekurzívan felsorolható prezentáció akinek szava probléma nem oldódik
• Minden végesen generált csoport rekurzívan felsorolható prezentációval és oldhatatlan szövegproblémával egy végesen előállított csoport alcsoportja, oldhatatlan szöveges problémával
• A végesen bemutatott, oldhatatlan szöveges problémával küzdő csoportok száma akár 14, sőt 12 is lehet.
• Az ésszerű rövid prezentáció egyértelmű példája megoldhatatlan szövegproblémával 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 {tömb}}}$

A szöveges feladat részleges megoldása

A rekurzívan bemutatott csoport szöveges problémája részben megoldható a következő értelemben:

Adott egy rekurzív előadás P = ⟨ X | R ⟩ egy csoport G , meghatározzák:

${\ displaystyle S = \ {\ langle u, v \ rangle: u {\ text {and}} v {\ text {szavak}} X {\ text {és}} u = v {\ text {in} } G \ \}}$

akkor van egy részleges rekurzív függvény f _P , amely:

${\ displaystyle f_ {P} (\ langle u, v \ rangle) = {\ begin {case} 0 & {\ text {if}} \ \ langle u, v \ rangle \ in S \\ {\ text {undefined/ nem áll meg}} \ & {\ text {if}} \ \ langle u, v \ rangle \ notin S \ end {case}}}$

Informálisabban, van egy algoritmus, amely leáll, ha u = v , de nem teszi ezt másként.

Ebből következik, hogy a P szöveges feladatának megoldásához elegendő egy olyan rekurzív függvényt konstruálni, hogy:

${\ displaystyle g (\ langle u, v \ rangle) = {\ begin {case} 0 & {\ text {if}} \ \ langle u, v \ rangle \ notin S \\ {\ text {undefined/nem áll meg }} \ & {\ text {if}} \ \ langle u, v \ rangle \ in S \ end {case}}}$

Azonban u = v G -ben akkor és csak akkor, ha uv ⁻¹ = 1 G -ben . Ebből következik, hogy, hogy megoldja a szó probléma P elegendő építésére egy rekurzív függvény H úgy, hogy:

${\ displaystyle h (x) = {\ begin {case} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined/nem áll meg}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {case}}}$

Példa

Ennek a technikának a használatára példaként a következőket fogjuk bizonyítani:

Tétel: Egy végesen bemutatott, maradékosan véges csoportnak megoldható szöveges feladata van.

Bizonyítás: Tegyük fel, G = ⟨ X | R ⟩ egy véges bemutatott, reziduálisan véges csoport.

Legyen S az N összes permutációjának , a természetes számoknak a csoportja , amely minden, de véges sok számot rögzít:

1. S van helyileg véges , és tartalmaz egy példányt minden véges csoport.
2. Az S szóbeli probléma megoldható a permutációk szorzatainak kiszámításával.
3. Az X véges halmaz S -be való leképezéseinek rekurzív felsorolása létezik .
4. Mivel G maradékul véges, ha w egy szó a G X generátorában , akkor w ≠ 1 G -ben, ha és csak X néhány S -re való leképezése olyan homomorfizmust idéz elő, hogy w ≠ 1 S -ben .

Tekintettel ezekre a tényekre, az algoritmust a következő pszeudokód határozza meg:

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

egy rekurzív függvényt h definiál, így:

${\ displaystyle h (x) = {\ begin {case} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined/nem áll meg}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {case}}}$

Ez azt mutatja, hogy G -nek megoldható szöveges problémája van.

Az egységes szöveges feladat megoldhatatlansága

A fentebb megadott kritérium, a szófeladat egyetlen csoportban való megoldhatóságához, egyszerű érvvel bővíthető. Ez megadja a következő kritériumot a szófeladat egységes megoldhatóságára egy végesen bemutatott csoportok osztálya esetén:

A csoportok K osztályának egységes szövegproblémájának megoldásához elegendő egy rekurzív függvényt találni , amely véges P prezentációt vesz fel egy G csoport számára, és egy szót a G generátorokban , úgy, hogy amikor G ∈ K : ${\ displaystyle f (P, w)}$${\ displaystyle w}$

${\ displaystyle f (P, w) = {\ begin {case} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined/nem áll meg }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ G \ end {case}}}$

Boone-Rogers-tétel: Nincs egységes parciális algoritmus, amely megoldja a szöveges feladatot minden végesen bemutatott csoportban, megoldható szöveges feladattal.

Más szóval, a megoldható szöveges problémával rendelkező, végesen bemutatott csoportok osztályának egységes szöveges feladata megoldhatatlan. Ennek érdekes következményei vannak. Például a Higman -beágyazási tétel felhasználható egy olyan csoport felépítésére, amely tartalmazza az izomorf másolatot minden végesen bemutatott, megoldható szövegproblémával rendelkező csoportról. Természetesnek tűnik a kérdés, hogy ennek a csoportnak lehetnek -e megoldható szöveges problémái. De ez a Boone-Rogers eredményének következménye, hogy:

Következtetés: Nincs univerzális megoldható szöveges feladatcsoport. Vagyis, ha G egy végesen bemutatott csoport, amely minden végesen előállított, megoldható szöveges feladattal rendelkező csoport izomorf másolatát tartalmazza, akkor magának G -nek is kell lennie megoldhatatlan szöveges feladatnak.

Megjegyzés: Tegyük fel, G = ⟨ X | R ⟩ jelentése véges bemutatott csoport megoldható szót problémát, és H egy véges részhalmaza G . Legyen H ^* = ⟨ H ⟩, legyen a csoport által generált H . Ezután a szó probléma H ^* megoldható: adott két szó h, k a generátorok H a H ^* , írd őket szava X és hasonlítsa össze őket a megoldás, hogy a szó probléma G . Könnyű azt gondolni, hogy ez a szófeladat egységes megoldását mutatja a végesen generált csoportok K (mondjuk) osztálya számára, amelyek G -be ágyazhatók . Ha ez így lenne, Boone-Rogers-ből könnyen következhetne az egyetemes megoldható szövegprobléma-csoport hiánya. Azonban a szöveges feladatra a K csoportokban most bemutatott megoldás nem egységes. Hogy ez, úgy egy csoport J = ⟨ Y | T ⟩ ∈ K ; ahhoz, hogy a fenti érvet felhasználva megoldjuk a J szöveges feladatot , először egy e: Y → G leképezést kell bemutatni, amely kiterjed az e ^* : J → G beágyazásra . Ha létezne egy rekurzív függvény, amely a K csoportok prezentációit (végesen előállított) a G beágyazásokra képezi le , akkor valóban létre lehet hozni a K -ban található szöveges feladat egységes megoldását . Általában azonban nincs ok azt feltételezni, hogy létezik ilyen rekurzív funkció. Azonban kiderült, hogy egy kifinomultabb érv a szó probléma J lehet oldani anélkül, hogy a beágyazó e : J → G . Ehelyett a homomorfizmusok felsorolását használjuk, és mivel egy ilyen felsorolás egységesen felépíthető, egységes megoldást eredményez a K -ban található szöveges feladatra .

Bizonyíték arra, hogy nincs univerzálisan megoldható szöveges feladatcsoport

Tegyük fel, hogy G egy univerzálisan megoldható szöveges feladatcsoport. Adott véges előadás P = ⟨ X | A H csoport R⟩ -jából rekurzívan felsorolhatjuk az összes h : H → G homomorfizmust, ha először felsoroljuk az összes h ^† : X → G leképezést . Ezek a leképezések nem mindegyike terjed ki a homomorfizmusokra, de mivel h ^† ( R ) véges, meg lehet különböztetni a homomorfizmusokat a nem homomorfizmusoktól, ha a G szóbeli feladat megoldását használjuk . A nem homomorfizmusok "kigyomlálása" megadja a szükséges rekurzív felsorolást: h ₁ , h ₂ , ..., h _n , ....

Ha H -nak megoldható szövegproblémája van, akkor a homomorfizmusok közül legalább egynek beágyazottnak kell lennie. Tehát adott egy w szót a H generátorokban :

${\ displaystyle {\ text {If}} \ w \ neq 1 \ {\ text {in}} \ H, \ h_ {n} (w) \ neq 1 \ {\ text {in}} \ G \ {\ SMS {néhánynak}} \ h_ {n}}$

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

Tekintsük az álkód által leírt algoritmust:

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.

Ez egy rekurzív függvényt ír le:

${\ displaystyle f (w) = {\ begin {case} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ H \\ {\ text {undefined/nem áll meg}} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ H. \ end {case}}}$

Az f függvény egyértelműen a P prezentációtól függ . Tekintettel arra, hogy ez a két változó függvénye, egy rekurzív függvényt állítottak elő, amely véges P prezentációt ad a H csoportnak és egy w szót a G csoport generátoraiban úgy, hogy amikor G -nek oldható szöveges problémája van: ${\ displaystyle f (P, w)}$

${\ displaystyle f (P, w) = {\ begin {case} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ H \\ {\ text {undefined/nem áll meg }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ H. \ end {case}}}$

De ez egységesen megoldja a szöveges feladatot az összes végesen előállított, megoldható szövegproblémával rendelkező csoport osztálya számára, ellentmondva Boone-Rogers-nek. Ez az ellentmondás bizonyítja, hogy G nem létezhet.

Algebrai szerkezet és a szöveges feladat

Számos eredmény kapcsolódik a szöveges feladat megoldhatóságához és az algebrai szerkezethez. Ezek közül a legjelentősebb a Boone-Higman-tétel :

Egy végesen bemutatott csoportnak akkor és csak akkor van megoldható szöveges problémája, ha beágyazható egy egyszerű csoportba , amely beilleszthető egy végesen bemutatott csoportba.

Széles körben elterjedt az a vélemény, hogy lehetővé kell tenni az építkezést úgy, hogy magát az egyszerű csoportot végesen mutassák be. Ha igen, akkor azt várnánk, hogy nehéz lesz bizonyítani, mivel az prezentációk egyszerű csoportokhoz való hozzárendelésének nem rekurzívnak kell lennie.

Bernhard Neumann és Angus Macintyre a következőket bizonyította :

Egy végesen bemutatott csoportnak akkor és csak akkor van megoldható szöveges problémája, ha minden algebrailag zárt csoportba beágyazható

Ebben az a figyelemre méltó, hogy az algebrai szempontból zárt csoportok annyira vadak, hogy egyiküknek sincs rekurzív bemutatása.

A legrégebbi eredmény, amely az algebrai struktúrát a szöveges feladat megoldhatóságához köti, Kuznyecov tétele:

Egy rekurzívan bemutatott egyszerű S csoportnak megoldható szöveges feladata van.

Ennek bizonyítására let ⟨ X | R ⟩ egy rekurzív bemutatót S . Válasszon egy ∈ S, hogy a ≠ 1 S .

Ha w egy szót a generátor X az S , akkor legyen:

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

Van egy rekurzív függvény, például: ${\ displaystyle f _ {{langle X | R \ cup \ {w \} \ rangle}}$

${\ displaystyle f _ {{langle X | R \ cup \ {w \} \ rangle} (x) = {\ begin {case} 0 & {\ text {if}} \ x = 1 \ {\ text {in}} \ S_ {w} \\ {\ text {undefined/nem áll meg}} \ & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ S_ {w}. \ End {case }}}$

Ír:

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

Aztán mivel az f felépítése egységes volt, ez két változó rekurzív függvénye.

Ebből következik, hogy: rekurzív. Felépítés szerint: ${\ displaystyle h (w) = g (w, a)}$

${\ displaystyle h (w) = {\ begin {case} 0 & {\ text {if}} \ a = 1 \ {\ text {in}} \ S_ {w} \\ {\ text {undefined/nem áll meg }} \ & {\ text {if}} \ a \ neq 1 \ {\ text {in}} \ S_ {w}. \ end {case}}}$

Mivel S egy egyszerű csoport, egyetlen hányados csoportja maga és a triviális csoport. Mivel egy ≠ 1 S , azt látjuk, a = 1, S _w , ha, és csak akkor, ha S _w triviális, ha, és csak akkor, ha W ≠ 1 S . Ezért:

${\ displaystyle h (w) = {\ begin {case} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ S \\ {\ text {undefined/nem áll meg}} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ S. \ end {case}}}$

Egy ilyen függvény megléte elegendő annak bizonyításához, hogy a S probléma megoldható .

Ez a bizonyítás nem bizonyítja, hogy létezik egységes algoritmus a szöveges feladat megoldására ebben a csoportcsoportban. Az egyenetlenség az egyszerű csoport nem triviális elemének kiválasztásában rejlik. Nincs ok azt feltételezni, hogy létezik egy rekurzív függvény, amely egy egyszerű csoport bemutatását a csoport nem triviális eleméhez rendeli. Azonban egy végesen bemutatott csoport esetében tudjuk, hogy nem minden generátor lehet triviális (Természetesen minden egyedi generátor lehet). Ennek a ténynek a felhasználásával módosítható a bizonyítás a következőképpen:

A szöveges feladat egységesen megoldható a végesen bemutatott egyszerű csoportok osztálya számára.

Lásd még

• A szavak kombinatorikája
• SQ-univerzális csoport
• Szöveges feladat (matematika)
• Elérhetőségi probléma
• Beágyazott verem -automaták (csoportos szöveges feladat megoldására használták)

Megjegyzések

Hivatkozások

• WW Boone, FB Cannonito és RC Lyndon . Szöveges feladatok: Döntési probléma a csoportelméletben. Hollandia: Észak-Hollandia. 1973.
• Boone, WW; Higman, G. (1974). "A szófeladat megoldhatóságának algebrai jellemzése" . J. Austral. Math. Soc . 18 : 41–53. doi : 10.1017/s1446788700019108 .
• Boone, WW; Rogers Jr, H. (1966). "A JHC Whitehead problémájáról és az Alonzo Church problémájáról" . Math. Scand . 19 : 185–192. doi : 10.7146/math.scand.a-10808 .
• Borisov, VV (1969), "Egyszerű példák a megoldhatatlan szöveges problémákkal küzdő csoportokra", Akademiya Nauk SSSR. Matematicheskie Zametki , 6 : 521–532, ISSN  0025-567X , MR  0260851
• Collins, Donald J. (1969), "Szó- és ragozási problémák csoportokban, amelyeknek csak néhány meghatározó kapcsolata van", 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 theorem 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), "Egy csoport egyszerű bemutatása megoldhatatlan szöveges problémával", Illinois Journal of Mathematics , 30 (2): 230–234, doi : 10.1215/ijm/1256044631 , ISSN  0019-2082 , MR  0840121
• Collins, Donald J .; Zieschang, H. (1990), Kombinatorikus csoportelmélet és alapvető csoportok , 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 Kuznyecov, "Algoritmusok, mint műveletek algebrai rendszerekben", Izvestija Akad. Nauk SSSR Ser Mat (1958)
• CF Miller. "Döntési problémák csoportok számára - felmérés és elmélkedések." Az Algoritmusok és osztályozás a kombinatorikus csoportelméletben , 1–60. Springer, 1991.
• Rotman, Joseph (1994), Bevezetés a csoportelméletbe , Berlin, New York: Springer-Verlag , ISBN 978-0-387-94285-8
• Stillwell, J. (1982). "A szóprobléma és az izomorfizmus probléma csoportok számára" . Az AMS közleménye . 6 : 33–56. doi : 10.1090/s0273-0979-1982-14963-1 .
• Nyberg-Brodda, Carl-Fredrik (2021), "A szóprobléma az egykapcsolati monoidok esetében: felmérés", Semigroup Forum , 103 (2): 297–355, arXiv : 2105.02853 , doi : 10.1007/s00233-021-10216 -8