Sanaryhmä ryhmille

Vuonna matematiikassa , tarkemmin alalla kombinatorisista ryhmä teoria , The sana ongelma varten äärellinen tyhmä G on algoritminen ongelma päätettäessä kaksi sanaa generaattorit ryhmän edustavat samoja elementtejä.

Erityisesti, jos X on äärellinen joukko generaattorit ja G , pidämme formaalin kielen koostuu sanoja X ja muodollisia käänteinen, jotka lähetetään luonnollinen sovelluksen identiteetin ryhmän G . Sanaongelma on algoritminen ongelma, joka koostuu sen päättämisestä, kuuluuko sana tähän viralliseen kieleen vai ei. Voimme nähdä, että jos Y on toinen joukko generaattoreita G: lle , niin sanan ongelma kaikella Y: llä vastaa sanan ongelmaa kaikilla X: llä . Siksi voimme puhua epäselvyydellä sanatehtävän ratkaistavuudesta rajallisen tyyppisen ryhmän G kohdalla.

Toisenlainen mutta siihen liittyviä ongelmia on yhtenäinen sana ongelma luokalle K ryhmien antaman rekursiivinen joukko esityksiä; algoritminen ongelma on päättää luokan K ryhmän G esityksen P perusteella , jos kaksi sanaa edustavat samaa G: n elementtiä . Voimme myös ajatella, että luokka K on määriteltävissä vain rekursiivisesti luetelluilla esitysjoukoilla .

Sanaongelma on ratkaisematon yleensä, mutta se on ratkaistavissa monille ryhmille. Esimerkiksi polysyklisillä ryhmillä (in) on ongelma ratkaistavissa oleva sana; samoin Todd-Coxeter -algoritmi ja Knuth-Bendix-täydennys antavat tehokkaita tuloksia. Toisaalta se, että tiettyä algoritmia ei sovelleta tietyssä tapauksessa, ei tarkoita, että sanaongelma on ratkaisematon. Esimerkiksi Dehnin algoritmi ei ratkaise toruksen perusryhmän sanaongelmaa , ja silti tämä ryhmä on kahden äärettömän syklisen ryhmän suora tulo, ja siksi sillä on ratkaiseva sanaongelma.

Tarkempi kuvaus

Tarkastellaan parin antamaa esitystä , jossa on generaattorijoukko ja relaattorijoukko. Sanaongelma on selvittää, edustavatko kaksi sanaa ja sen käänteisosa samaa elementtiä modulo-ryhmän relaattoreissa. Formaalisemmin anna ryhmä äärellinen tyyppiä , antama esitys , jossa äärellinen X. Tarkastelemme aakkosia , joissa on erottamaton aakkoset ja jotka ovat yhdessä niiden kanssa ; sen elementit edustavat muodon käänteisiä elementtejä . Pidämme karttaa kuin tuottaa , täydentämisen surjective morfismi vapaan monoidi päälle . Sana ongelma muodostuu siis määrittää, onko , jossa jos kaksi sanaa ja , ja jossa on muodollinen käänteinen in ja jossa on neutraali osa . Vastaavasti ongelma on päättää, jos sanaa on , joten jos kuuluu virallisen kielen ${\ displaystyle (X \ puolivälissä R)}$ $X$ $R$ $X$ $G$ ${\ displaystyle G = \ langle X \ mid R \ rangle}$ ${\ displaystyle \ Sigma = X \ sqcup X ^ {- 1}}$ ${\ displaystyle X ^ {- 1}}$ $X$ $X$ $X$ ${\ displaystyle \ pi: X \ - G}$ ${\ displaystyle \ pi (X) \ subseteq G}$ $G$ $\ Sigma ^ {*}$ $G$ ${\ displaystyle \ pi (u) = \ pi (v)}$ ${\ displaystyle \ pi (uv ^ {- 1}) = e}$ $u$ $v$ ${\ displaystyle v ^ {- 1}}$ $v$ $\ Sigma ^ {*}$ $e$ $G$ ${\ displaystyle \ pi (x) = e}$ $x$ $\ Sigma ^ {*}$ $x$

{\ displaystyle W (G, X) = \ {w \ sisään \ Sigma ^ {*} \ mid \ pi (w) = e \}}

Hieman elliptisen lyhenteen avulla sanomme myös, että kokonaisuus on sanan ongelma. Sanomme myös, että sanaongelma on ratkaistavissa, jos kielijäsenyys on ratkaistavissa. ${\ displaystyle W (G, X)}$ ${\ displaystyle W (G, X)}$

Esimerkkejä

Ryhmät, joilla on ratkaistava sanaongelma

Seuraavilla ryhmillä on ratkaistava sanaongelma:

Automaattinen ryhmiä , joita ovat:
- rajallinen ryhmien
- hyperbolinen ryhmät
- euklidinen ryhmät
- Coxeter ryhmät
- punos ryhmien
- geometrisesti rajallinen ryhmät (in)
Vapaata ryhmää finitely
Abelin ryhmien rajallinen tyyppi
Polysykliset ryhmät (in)
Ryhmät esitetään täysin (in) äärellinen tyyppi, joka käsittää:
- Yksinkertaiset äärellisen tyyppiset ryhmät.
Jäljellä olevat äärelliset ryhmät (sisään) hienosti esitetyt
Ryhmät relaattorissa (Magnus-lause), mukaan lukien lajikkeiden perusryhmät, kaksi ulottuvuutta ja säädettävät suljetut.
Käytännöllisesti katsoen vapaata ryhmää on rajallinen tyyppiä, koska kieli vastaavat sanat neutraali elementti on algebrallinen kieli , jota Muller-Schupp lause .

Ryhmät, joilla on ratkaisematon sanaongelma

Olkoon X rekursiivisesti numeroituva joukko luonnollisia kokonaislukuja, joissa jäsenyysongelma on ratkaisematon. Joten ryhmä ${\ displaystyle \ langle a, b, c, d \ mid a ^ {n} ba ^ {n} = c ^ {n} dc ^ {n}, n \ X-ranglessa}$ on äärellisen tyyppinen, rekursiivisesti lueteltava esitys ja jonka sanaongelma on ratkaisematon.
Mikä tahansa äärellisen tyyppinen ryhmä, jossa on rekursiivisesti numeroitava esitys ja ratkaisematon sanaongelma, on alaryhmä äärellisestä tyyppiryhmästä, jossa on ratkaisematon sanaongelma
Relaattoreiden määrä hienosti esitetyssä ryhmässä, jolla on ratkaisematon sanaongelma, voi olla 14 tai jopa 12.
Selkeä esimerkki esityksestä, jolla on ratkaisematon sanaongelma, on:

generaattorit :

{\ displaystyle \ {a, b, c, d, e, p, q, r, t, k \}}

suhteet : (kommutaatiot) ja paljon muuta

{\ displaystyle ra = ar, rb = br, rc = cr, rd = dr, re = er, pt = tp, qt = tq}

{\ displaystyle {\ begin {array} {ll} & p ^ {10} a = ap, & pacqr = rpcaq, \\ & p ^ {10} b = bp, & p ^ {2} adq ^ {2} r = rp ^ {2} daq ^ {2}, \\ & p ^ {10} c = cp, & p ^ {3} bcq ^ {3} r = rp ^ {3} cbq ^ {3}, \ \ & p ^ {10} d = dp, & p ^ {4} bdq ^ {4} r = rp ^ {4} dbq ^ {4}, \\ & p ^ {10} e = ep ja {5} ceq ^ {5} r = rp ^ {5} ecaq ^ {5}, \\ & aq ^ {10} = qa, & p ^ {6} deq ^ {6} r = rp ^ {6} edbq ^ {6}, \\ & bq ^ {10} = qb, & p ^ {7} cdcq ^ {7} r = rp ^ {7} cdceq ^ {7}, \\ & cq ^ {10} = qc, & p ^ {8} ca ^ {3} q ^ {8} r = rp ^ {8} a ^ {3} q ^ {8}, \\ & dq ^ {10} = qd ja & p ^ {9} da ^ {3} q ^ {9} r = rp ^ {9} a ^ {3} q ^ {9}, \\ & eq ^ {10} = qe ja a ^ {- 3} ta ^ {3} k = ka ^ {- 3} ta ^ {3} \ end {array}}}

Yleiset tulokset

Boone-Rogersin lause : Ei ole olemassa osittaista algoritmia, joka ratkaisisi sanatehtävän kaikissa rajallisissa tyyppiryhmissä, joissa on ratkaistavissa oleva sanatehtävä.

Toisin sanoen yhtenäinen sanaongelma ei ole ratkaistavissa kaikkien lopullisesti esitettyjen ryhmien luokassa.

Boone-Higman-lause : Hienolla esitetyllä ryhmällä on ratkaistavissa oleva sanatehtävä vain ja vain, jos se voidaan upottaa yksinkertaiseksi ryhmäksi, joka voidaan upottaa hienoksi esitettyyn ryhmään.

Seuraavan tuloksen ovat osoittaneet Bernhard Neumann ja Angus Macintyre :

Lopullisesti esitetyllä ryhmällä on sanaongelma ratkaistavissa vain ja vain, jos se voidaan upottaa mihin tahansa algebrallisesti suljettuun ryhmään (sisään) .

Yksittäisille ryhmille:

Yhdellä rekursiivisesti esitetyllä ryhmällä on ratkaistava sanaongelma.

Sanaongelma on yhtenäisesti ratkaistavissa hienoksi esitettyjen yksinkertaisten ryhmien luokassa.

Historiallinen huomautus

Ryhmälaskelmat tehdään usein erilaisilla normaalimuodoilla . Tällaisen normaalin muodon olemassaolo ratkaisee implisiittisesti tutkittujen ryhmien sanaongelman. Vuonna 1911 Max Dehn ehdotti, että sanaongelma pidettäisiin sinänsä tärkeänä tutkimusaiheena, samoin kuin taivutusongelma (en) ja ryhmien isomorfismin ongelma (en) . Vuonna 1912 hän antoi algoritmin sanatehtävän ja konjugaatio-ongelman ratkaisemiseksi suvun ulottuvuuden 2 suuntautuvien, suuntautuvien suljettujen jakotukkien perusryhmille, jotka ovat suurempia tai yhtä suuria kuin 2. Muut kirjoittajat laajensivat sitten suuresti Dehnin algoritmia ja soveltivat sitä moniin päätösongelmiin .

Vuonna 1955 Piotr Novikov osoittaa, että on olemassa hienosti esitetty ryhmä G, jonka sanaongelma on ratkaisematon . Tästä seuraa välittömästi, että myös yhtenäinen sanaongelma on ratkaisematon. William Boone antoi riippumattoman todistuksen vuonna 1958.

Sanaongelma oli yksi ensimmäisistä esimerkeistä ratkaisemattomasta ongelmasta, joka ei johtunut matemaattisesta logiikasta tai algoritmien teoriasta , vaan yleisestä algebrasta , joka on klassisen matematiikan keskeinen osa.

Huomautuksia ja viitteitä

Huomautuksia

JA Todd ja HSM Coxeter. "Käytännön menetelmä äärellisen abstraktin ryhmän kosetin laskemiseksi", Proc. Edinburgh Math Soc. (2), voi. 5, sivut 25-34, 1936.
D. Knuth ja P. Bendix. "Yksinkertaiset sanaongelmat universaaleissa algebroissa", J. Leech (toimittaja) Computational Problems in Abstract Algebra , sivut 263-297, 1970.
H. Simmons, "Absoluuttisten esitysten sanaongelma." J. London Math. Soc. (2) 6, 275 - 280, 1973
Lyndon ja Schupp 2001 .
Collins ja Zieschang 1990 , s. 149.
Collins ja Zieschang 1990 , Cor. 7.2.6.
Collins 1969 .
Borisov 1969 .
Collins 1972 .
Collins 1986 .
Esitetty versio on korjattu versio, joka on otettu John Pedersenin luettelosta Algebraic Systems .
Dehn 1911 .
Dehn 1912 .
Martin Greendlinger , " Dehnin algoritmi sanatehtävälle ", puhtaan ja sovelletun matematiikan tiedonannot , voi. 13, n o 1, Kesäkuu 1959, s. 67–83 ( DOI 10.1002 / cpa.3160130108 )
Roger C. Lyndon , ” Dehnin algoritmista ”, Mathematische Annalen , voi. 166, n ° 3, Syyskuu 1966, s. 208–228 ( DOI 10.1007 / BF01361168 , lue verkossa )
Paul E. Schupp , ” Dehnin algoritmista ja konjugaatio-ongelmasta ”, Mathematische Annalen , voi. 178, n ° 2 Kesäkuu 1968, s. 119–130 ( DOI 10.1007 / BF01350654 , lue verkossa )
Novikov 1955 .
Boone 1958 .

Viitteet

(en) " Word-ongelma " , PlanetMathissa

Kirjat

Roger C.Lyndon ja Paul E.Schupp , yhdistelmäryhmäteoria , Springer-Verlag , coll. "Matematiikan klassikot",2001, xiv + 339 Sivumäärä ( ISBN 3-540-41158-5 , lue verkossa ) - Uusintapainos vuoden 1977 painoksesta
William W. Boone, FB Cannonito ja Roger C. Lyndon (toimittajat), Word ongelmat: Päätös Ongelma ryhmässä teoria , Pohjois-Hollanti,1973.
Joseph Rotman , Johdatus ryhmien teoriaan , Berliini, New York, Springer-Verlag ,1994, 517 Sivumäärä ( ISBN 978-0-387-94285-8 , lue verkossa ).
Donald J. Collins ja H. Zieschang , Kombinatoriset ryhmä teoria ja perusoikeuksien ryhmiä , Berliinissä, New Yorkissa, Springer-Verlag ,1990( Matemaattiarvostelut 1099152 )

Artikkelit

(ru) Piotr Novikov , " Sanatehtävän algoritmisesta ratkaisemattomuudesta ryhmateoriassa " , Proceedings of the Steklov Institute of Mathematics , voi. 44,1955, s. 1-143 ( zbMATH 0068,01301 )
William W. Boone , ” Sana ongelma ” Proceedings of the National Academy of Sciences , vol. 44, n ° 10,1958, s. 1061–1065 ( DOI 10.1073 / pnas.44.10.1061 , zbMATH 0086.24701 , lue verkossa [PDF] )
William W. Boone ja G. Higman, " Algebrallinen luonnehdinta sanatehtävän ratkaistavuudelle ", J.Austral. Matematiikka. Soc. , voi. 18,1974, s. 41 - 53.
William W. Boone ja H. Rogers Jr., ” JHC Whiteheadin ongelmasta ja Alonzo Churchin ongelmasta ”, Math. Scand. , voi. 19,1966, s. 185-192.
VV Borisov , " Yksinkertaisia esimerkkejä ryhmistä, joilla on ratkaisematon sanaongelma ", Akademiya Nauk SSSR. Matematicheskie Zametki , voi. 6,1969, s. 521–532 ( ISSN 0025-567X , matemaattiset arvostelut 0260851 )
Donald J. Collins , " Sana- ja taivutusongelmat ryhmissä, joissa on vain muutama määrittävä suhde ", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , voi. 15, n os 20-221969, s. 305–324 ( DOI 10.1002 / malq.19690152001 , matemaattiset arvostelut 0263903 )
Donald J. Collins , ” VV Borisovin teoreemaa upottavasta ryhmästä ”, Bulletin of London Mathematical Society , voi. 4, n o 21972, s. 145–147 ( ISSN 0024-6093 , DOI 10.1112 / blms / 4.2.145 , matemaattiset arvostelut 0314998 )
Donald J. Collins , " Yksinkertainen esitys ryhmästä, jolla on ratkaisematon sanaongelma ", Illinois Journal of Mathematics , voi. 30, n o 21986, s. 230–234 ( ISSN 0019-2082 , matemaattiset arvostelut 840121 )
Max Dehn , " Über unendliche diskontinuierliche Gruppen ", Mathematische Annalen , voi. 71, n o 1,1911, s. 116–144 ( ISSN 0025-5831 , DOI 10.1007 / BF01456932 , matemaattiset arvostelut 1511645 , lue verkossa )
Max Dehn , " Transformation der Kurven auf zweiseitigen Flächen ", Mathematische Annalen , voi. 72, n ° 3,1912, s. 413–421 ( ISSN 0025-5831 , DOI 10.1007 / BF01456725 , matemaattiset arvostelut 1511705 , lue verkossa )
CF Miller, ”Ryhmien päätöksenteko-ongelmat - tutkimus ja pohdinnat” , julkaisussa Algoritmit ja luokittelu yhdistelmäryhmäteoriassa , Springer,1991, s. 1-60
J. Stillwell, " Sanaongelma ja ryhmien isomorfismiongelma ", AMS Bulletin , voi. 6,1982, s. 33-56.
Sam AM Jones ja Richard M. Thomas , ” Ryhmien tekstiongelmat: muodolliset kielet, luonnehdinnat ja päätettävyys ”, teoreettinen tietojenkäsittelytiede , voi. 750,2018, s. 2–23 ( DOI 10.1016 / j.tcs.2018.05.007 ).

Aiheeseen liittyvät artikkelit

Sanojen yhdistelmä
Word-ongelma
Sisäkkäinen akkuautomaatti (niitä käytettiin sanatehtävän ratkaisemiseen ryhmissä)