Muller-Schuppin lause

In matematiikan ja teoreettisen tietojenkäsittelyopin , The Muller-Schupp teoreema toteaa, että ryhmä G on äärellinen tyyppi on sana ongelma ryhmille , joka on algebrallinen kieli , jos ja vain jos se on lähes ilmainen . Lauseen esittivät ensimmäisen kerran David E. Muller ja Paul E. Schupp vuonna 1983. Siitä lähtien muita todisteita on annettu.

Lause

Sanaryhmä ryhmille

Sana ongelma varten rajallinen tyypin ryhmä G on algoritminen ongelma päätettäessä kaksi sanaa generaattorit edustavat samoja elementtejä. Olkoon ryhmä rajallinen tyyppiä voidaan antaa vain esitys , jossa rajallinen X. Tarkemmin sanottuna, jos X äärellinen joukko generaattorit ja G , niin sana ongelma on algoritminen ongelma jäsenyys sananen X ja sen inverssit on muodollista kieltä , joka koostuu sanoja X ja se on perustettu d 'muodolliset käänteet, jotka luonnollinen sovellus lähettää ryhmän G identiteettiin . Pidämme X : tä aakkosena, jolla on morfismi , joka tuottaa . Annetaan , missä on erillinen kopio ; sitten ulottuu surjektiiviseksi monoidimorfismiksi vapaasta monoidista eteenpäin . Sana ongelma sitten koostuu määrittää, onko , tai 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 $G$ ${\ displaystyle G = \ langle X \ mid R \ rangle}$ ${\ displaystyle \ pi: X \ - G}$ ${\ displaystyle \ pi (X) \ subseteq G}$ $G$ ${\ displaystyle \ Sigma _ {X} = X \ sqcup X ^ {- 1}}$ ${\ displaystyle X ^ {- 1}}$ $X$ ${\ displaystyle \ pi: X \ - G}$ ${\ displaystyle \ Sigma _ {X} ^ {*}}$ $G$ ${\ displaystyle \ pi (u) = \ pi (v)}$ ${\ displaystyle \ pi (uv ^ {- 1}) = e}$ $u$ $v$ ${\ displaystyle v ^ {- 1}}$ $v$ ${\ displaystyle \ Sigma _ {X} ^ {*}}$ $e$ $G$ ${\ displaystyle \ pi (x) = e}$ $x$ ${\ displaystyle \ Sigma _ {X} ^ {*}}$ $x$

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

Hieman elliptisen pikakuvakkeen osalta sanomme myös, että kokonaisuus on X: n yli olevan sanan ongelma . Olemme myös sanoa, että sana ongelma on ratkaistavissa , jos kieli jäsenyys on ratkeava. ${\ displaystyle {\ mathcal {W}} (G, X)}$ $G$ ${\ displaystyle {\ mathcal {W}} (G, X)}$

Lähes vapaa ryhmä

Ryhmä on käytännössä vapaa, jos sillä on vapaa aliryhmä rajallisesta indeksistä. Emäs tuloksia Bass-Serre teoria (in) sanoi äärellisesti tuotettu ryhmä on käytännöllisesti katsoen ilmaiseksi, jos ja vain jos factorises keskeisinä ryhmä on kuvaaja ryhmiä . $G$ $G$ $G$ $G$

Kontekstiton ryhmä

Ryhmän sanotaan olevan "kontekstivapaa", jos sen sanaongelma on algebrallinen kieli ("kontekstiton"). $G$

Lauseen lause

Lause on esitetty seuraavasti:

Lause - Antaa olla äärellinen tyyppinen ryhmä, jossa on joukko generaattoreita . Sitten se on käytännössä ilmainen vain ja vain, jos sen sanaongelma on algebrallinen kieli . $G$ $X$ $G$ ${\ displaystyle {\ mathcal {W}} (G, X)}$

Vastaava formulaatio on:

Vastaava muotoilu - Rajallinen tyyppiryhmä on kontekstivapaa vain ja vain, jos se on käytännössä ilmainen.

Muut todisteet

Vuoden 1983 artikkelin jälkeen on annettu useita muita todisteita Muller-Schupp-lauseesta. Yksityiskohtainen esittely on Diekertin ja Weißin minikurssin teksti.
Muller-Schupp-lause on huomattava yleistys Anisimov-lauseesta vuodelta 1971, jossa todetaan, että äärelliselle tyyppiryhmälle G, jolla on äärellinen generaattorijoukko X , sanan sanaongelma on järkevä kieli vain ja jos ryhmä G on valmis . ${\ displaystyle {\ mathcal {W}} (G, X)}$
Lause on vuonna 1983 julkaistun artikkelin muotoilussa vähemmän yleinen, koska siinä käytetään rajallisen tyyppisten ryhmien esteettömyyden käsitettä; Alkuperäisessä lausunnossa sanotaan, että ryhmä on käytännössä vapaa vain ja vain, jos se on käytettävissä ja sen sanaongelma on algebrallinen kieli. Siitä lähtien tämä hypoteesi on poistettu.

Sovellukset

Eräässä toisessa artikkelissa Muller ja Schupp osoittavat, että hienosti generoidulla kuvaajalla Γ on vain rajallinen määrä loppuisomorfisia tyyppejä vain ja vain, jos Γ on alaspäin laskevan automaatin siirtymäkaavio . Tämän seurauksena ne osoittavat, että kontekstittoman kaavion toisen asteen monadinen logiikka (kuten käytännöllisesti katsoen vapaan ryhmän Cayley-kaavio) on ratkaistavissa, mikä yleistää Rabinin lauseen binääripuista. Myöhemmin Kuske ja Lohrey osoittivat, että käytännössä vapaat ryhmät ovat ainoat rajalliset tyyppiryhmät, joiden Cayley-kaavioilla on ratkaiseva monadinen teoria.

Géraud Sénizergues käyttää Muller - Schupp -lausetta osoittaakseen, että ryhmän isomorfismiongelma (en) on primitiivinen rekursiivinen käytännöllisesti katsoen vapaille rajallisen tyyppisille ryhmille.

Gilman, Hermiller, Holt ja Rees osoittavat Muller - Schupp-lauseen avulla, että rajallinen tyyppiryhmä on käytännössä vapaa, jos on olemassa joukko uudelleenkirjoitussääntöjä, joiden pituus pienenee generaattorien X joukolle, joiden sovellus toistaa, mikä tahansa sana geodeettiseksi sana.

Broughin Muller - Schupp-lauseen laajennus käsittelee ryhmiä, joiden sanaongelma on rajallisen määrän algebrallisia kieliä.

Huomautuksia ja viitteitä

(fr) Tämä artikkeli on osittain tai kokonaan peräisin englanninkielisestä Wikipedia- artikkelista ” Muller - Schupp-lause ” ( katso kirjoittajaluettelo ) .

David E. Muller ja Paul E. Schupp, ” Ryhmät, pääteoria ja kontekstittomat kielet ”, Journal of Computer and System Sciences , voi. 26, n ° 3, 1983, s. 295-310 ( lue verkossa ).
A. Karrass , A. Pietrowski ja D. Solitar , " Finite ja ääretön syklinen laajennukset vapaata ryhmää " Australian Mathematical Society , voi. 16, n ° 04,2009, s. 458 ( ISSN 1446-7887 , DOI 10.1017 / S1446788700015445 )
Volker Diekert ja Armin Weiß , " Kontekstivapaat ryhmät ja Bass-Serren teoria ", Kesäkoulu vapaiden ryhmien automorfismeista , 25.-29. Syyskuuta 2012 ( arXiv 1307.8297 )
Termi "kontekstiton" käännetään ranskaksi yleensä "algebralliseksi", mutta sana algebrallinen ryhmä osoittaa matematiikassa toisen objektin.
Volker Diekert ja Armin Weiß , ” Kontekstivapaat ryhmät ja niiden rakennepuut ”, International Journal of Algebra and Computation , voi. 23, n o 03, 2013, s. 611–642 ( ISSN 0218-1967 , DOI 10.1142 / S0218196713500124 , arXiv 1202.3276 )
Yago Antolín, " Käytännössä vapaiden ryhmien Cayley-kaavioissa ", Groups, Complexity, Cryptology , voi. 3, n o 22011, s. 301-327 ( matemaattiset arvostelut 2898895 ).
T. Ceccherini-Silberstein ja W. Woess, Ryhmien I kontekstittomat parit: Kontekstittomat parit ja kuvaajat . European Journal of Combinatorics 33 (2012), nro. 7, 1449 - 1466
(ru) Anatoli V. Anisimov, " Ryhmän kielet " , Kibernetika (Kiova) , vol. 4,1971, s. 18–24 ( matemaattiset arvostelut 301981 ).
David E. Muller ja Paul E. Schupp , " Teorian päädyt, alasajettavat automaatit ja toisen asteen logiikka ", Theoretical Computer Science , voi. 37, n o 1,1985, s. 51-75 ( ISSN 0304-3975 , DOI 10,1016 / 0304-3975 (85) 90087-8 ).
Michael O. Rabin, ” Äärettömien puiden toisen asteen teorioiden ja automaattien ratkaistavuus ”, Transaction of the American Mathematical Society , voi. 141,1969, s. 1-35 ( lue verkossa ).
Dietrich Kuske ja Markus Lohrey , " Cayley-graafien loogiset näkökohdat: ryhmän tapaus ", Annals of Pure and Applied Logic , voi. 131, n luu 1-3,2005, s. 263-286 ( ISSN 0168-0072 , DOI 10.1016 / j.apal.2004.06.002 ).
Géraud Sénizergues, "Kontekstittoman ryhmän rajallisista alaryhmistä" , julkaisussa Geometric and computational perspectives on infinite groups (Minneapolis, MN ja New Brunswick, NJ, 1994) , American Mathematical Society , Providence, RI ,, coll. “DIMACS Ser. Diskreetti matematiikka. Teoria. Laske. Sci. "( N- o- 25), 1996, s. 201-212
RH Gilman, S. Hermiller, D. Holt ja S. Rees, ” Lähes vapaiden ryhmien luonnehdinta ”, Archiv der Mathematik , voi. 89, n o 4,2007, s. 289 - 295.
T. Brough ” Ryhmät poly-yhteydett sana ongelma ” ryhmät, monimutkaisuus, Kryptologia , vol. 6, n o 1,2014, s. 9-29.

Aiheeseen liittyvät artikkelit

Ulkoinen linkki

Armin Weiß, "Kontekstittomat ryhmät ja niiden rakennepuut" - Transparents d'un -näyttely, 2013.