Ecuația dintre cuvinte

În matematică și informatică teoretică , și mai ales în combinatorie de cuvinte , o ecuație de cuvinte sau o ecuație între cuvinte (în engleză ecuație de cuvinte ) este o pereche de cuvinte , de obicei scrise sub forma unei ecuații (U,V){\ displaystyle (U, V)}

U=V{\ displaystyle U = V}.

Iată și sunt cuvinte formate din litere care sunt constante sau variabile. Constantele sunt scrise cu litere mici și variabile cu majuscule sau, de asemenea, frecvent cu litere mici de „necunoscute”, cum ar fi etc. De exemplu, ecuația U{\ displaystyle U}V{\ displaystyle V}X,y,z{\ displaystyle x, y, z}

labXbX=XbXbla{\ displaystyle abXbX = XbXba}

conține patru apariții ale variabilei , și constantele și . O soluție a unei ecuații este un set de cuvinte fără variabile, unul pentru fiecare variabilă, astfel încât înlocuirea cuvintelor cu variabile face ca cele două componente ale ecuației să fie aceleași. De exemplu, pentru (și mai general pentru cu , cele două laturi precedente ale ecuației devin egale cu (și mai general cu ). X{\ displaystyle X}la{\ displaystyle a}b{\ displaystyle b}X=la{\ displaystyle X = a}X=(lab)kla{\ displaystyle X = (ab) ^ {k} a}k≥0{\ displaystyle k \ geq 0}lablabla{\ displaystyle ababa}(lab)2k+2la{\ displaystyle (ab) ^ {2k + 2} a}

Considerăm problema găsirii unei soluții cu o ecuație de cuvinte sau, mai general, cu un set de ecuații de cuvinte. O celebră teoremă Makanin stabilește că această problemă este decisivă . În acest sens, ecuațiile cuvântului se disting de ecuațiile diofantine pentru care existența soluțiilor este indecidabilă prin teorema lui Matiassevitch care rezolvă a zecea problemă a lui Hilbert .

O problemă conexă este descrierea tuturor soluțiilor unei ecuații date, de obicei sub formă parametrizată. Primul studiu sistematic în această direcție este realizat de Hmelevskii.

Formulare

O ecuație este o pereche de cuvinte pe un alfabet alcătuit din constante și variabile. O soluție este un morfism al monoizilor care asociază cu fiecare variabilă X un cuvânt f (X) și care lasă constantele neschimbate și care satisface (U,V){\ displaystyle (U, V)}f{\ displaystyle f}

f(U)=f(V){\ displaystyle f (U) = f (V)}.

Astfel, pentru exemplul ecuației date în introducere, morfismul definit de este o soluție. De asemenea, uneori scriem pentru acest morfism, litera aleasă trebuind să amintească cuvântul „soluție” sau mai simplu . (labXbX,XbXbla){\ displaystyle (abXbX, XbXba)}f(X)=la{\ displaystyle f (X) = a}S{\ displaystyle S}X=la{\ displaystyle X = a}

O ecuație fără constantă este o ecuație care conține numai variabile, cum ar fi ecuația . (XDa,DaX){\ displaystyle (XY, YX)}

Se obișnuiește identificarea variabilelor (notate cu majuscule) cu soluții (notate cu litere mici). Deci, în loc să vorbim despre ecuație , vorbim despre verificarea cuvintelor . De asemenea, este mai natural să scrieți în loc de . (XDa,DaX){\ displaystyle (XY, YX)}X,y{\ displaystyle x, y}Xy=yX{\ displaystyle xy = yx}U=V{\ displaystyle U = V}(U,V){\ displaystyle (U, V)}

O soluție a unei ecuații se spune că este ciclică (sau periodică ) dacă toate cuvintele sale sunt puteri ale aceluiași cuvânt. De exemplu, soluțiile ecuației

XDa=DaX{\ displaystyle XY = YX}

sunt toate ciclice.

Se spune că o ecuație este pătratică dacă orice variabilă apare cel mult de două ori. Iată un exemplu de ecuație pătratică în 4 variabile  : X,Da,Z,T{\ displaystyle X, Y, Z, T}

XlaTZlaT=DaZbXlalabDa{\ displaystyle XaTZaT = YZbXaabY}

O soluție este dată de:

X=labb,Da=lab,Z=bla,T=blab{\ displaystyle X = abb, Y = ab, Z = ba, T = bab}

și într-adevăr avem:

(labb)la(blab)(bla)la(blab)=labblablabblalablab=(lab)(bla)b(labb)lalab(lab){\ displaystyle (abb) a (bab) (ba) a (bab) = abbababbaabab = (ab) (ba) b (abb) aab (ab)}.

Ecuații între cuvinte și ecuații diofantine

Ecuațiile dintre cuvinte sunt legate de ecuațiile diofantine . Putem pur și simplu codifica o ecuație între cuvinte într-o ecuație diofantină, pe baza faptului că matricile

(1011){\ displaystyle {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}}} și (1101){\ displaystyle {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix}}}

generează un monoid liber și, în plus, acestea sunt exact matricile de ordinul 2 al grupului special liniar cu coeficienți întregi naturali. SL⁡(2,Z){\ displaystyle \ operatorname {SL} (2, \ mathbb {Z})}

Astfel, ecuația

labX=Dabla{\ displaystyle abX = Yba}

are o soluție dacă și numai dacă următorul sistem de ecuații diofantine cu 8 necunoscute are o soluție întreagă: X1,...,Da4{\ displaystyle X_ {1}, \ ldots, Y_ {4}}

(1011)⋅(1101)⋅(X1X2X3X4)=(Da1Da2Da3Da4)(1101)⋅(1011)X1X4-X2X3=1Da1Da4-Da2Da3=1Xeu≥0,Daeu≥0(1≤eu≤4){\ displaystyle {\ begin {align} {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix} } \ cdot {\ begin {pmatrix}}} X_ {1} & X_ {2} \\ X_ {3} & X_ {4} \ end {pmatrix}} & = {\ begin {pmatrix} Y_ {1} & Y_ {2} \\ Y_ {3} & Y_ {4} \ end {pmatrix}} {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}} \\ X_ {1} X_ {4} -X_ {2} X_ {3} & = 1 \\ Y_ {1} Y_ {4} -Y_ {2} Y_ {3} & = 1 \\ X_ {i} \ geq 0, Y_ {i} \ geq 0 & \ quad (1 \ leq i \ leq 4) \ end {align}}}

Dar, în timp ce a zecea problemă a lui Hilbert , și anume determinarea dacă o ecuație diofantină are o soluție, este indecidabilă, găsirea unei soluții a unei ecuații între cuvinte este decisă de teorema lui Makanin.

Complexitate

Teorema lui Makanin spune problema de a determina dacă o ecuație are o soluție decisivă. Complexitatea algoritmului de decizie a făcut obiectul multor cercetări; în 1999, Plandowski a arătat că problema se află în clasa de complexitate numită PSPACE .

O nouă abordare a problemei este prezentată de Artur Jeż în 2013. El folosește o metodă de modificare locală a variabilelor care constă, pe de o parte, în înlocuirea unei variabile cu sau după caz, și, pe de altă parte, în înlocuirea unei perechi de litere care apar în ecuație cu o nouă literă. Cu această tehnică, el obține un algoritm nedeterminist în spațiu și în timp polinomial în și , unde este lungimea ecuației și este dimensiunea celei mai scurte soluții a ecuației. Această dimensiune este în sine dublu exponențială în . X{\ displaystyle X}laX{\ displaystyle aX}Xla{\ displaystyle Xa}O(nuButuruga⁡nu){\ displaystyle O (n \ log n)}NU{\ displaystyle N}nu{\ displaystyle n}nu{\ displaystyle n}NU{\ displaystyle N}NU{\ displaystyle N}nu{\ displaystyle n}

Exemple de ecuații fără constante

În aceste exemple, luăm în considerare doar soluțiile alcătuite din cuvinte care nu sunt goale. Cele mai simple ecuații fără constante au adesea soluții destul de ușor de descris.

Ecuații în două variabile

Pentru două variabile, avem rezultatul general:

Soluțiile unei ecuații fără constante în două variabile sunt toate ciclice

Putem fi mai preciși: pentru o ecuație fără constante

U=V{\ displaystyle U = V}

unde conține apariții și apariții și unde conține apariții și apariții ale , soluțiile sunt toate de formă , pentru un cuvânt și întregi cu . U{\ displaystyle U}nu{\ displaystyle n}X{\ displaystyle X}m{\ displaystyle m}Da{\ displaystyle Y}V{\ displaystyle V}p{\ displaystyle p}X{\ displaystyle X}q{\ displaystyle q}Da{\ displaystyle Y}X=teu,Da=tj{\ displaystyle X = t ^ {i}, Y = t ^ {j}}t{\ displaystyle t}eu,j{\ displaystyle i, j}nueu+mj=peu+qj{\ displaystyle ni + mj = pi + qj}

Ecuații cu trei variabile

Cazul ecuațiilor cu trei variabile este mai complex. Un prim exemplu este ecuația

XZ=ZDa{\ displaystyle XZ = ZY}

Soluțiile acestei ecuații sunt de formă pentru cuvinte și un număr întreg . Cuvintele soluții pentru și sunt, prin urmare, cuvinte conjugate . X=pq,Da=qpZ=(pq)nup{\ displaystyle X = pq, Y = qpZ = (pq) ^ {n} p}p,q{\ displaystyle p, q}nu≥0{\ displaystyle n \ geq 0}X{\ displaystyle X}Da{\ displaystyle Y}

Soluții la ecuație

XDaZ=ZDaX{\ displaystyle XYZ = ZYX}

sunt de forma . X=(pq)eup,Da=(q(pq)j,Z=(pq)kp{\ displaystyle X = (pq) ^ {i} p, Y = (q (pq) ^ {j}, Z = (pq) ^ {k} p}

Soluțiile ecuației sunt de formă . XDaZ=ZXDa{\ displaystyle XYZ = ZXY}X=(pq)eu,Da=q(pq)j,Z=(pq)k{\ displaystyle X = (pq) ^ {i}, Y = q (pq) ^ {j}, Z = (pq) ^ {k}}

O teoremă generală, demonstrată de Hmelevskii, este următoarea:

Soluțiile unei ecuații fără constante în trei variabile sunt fin parametrizabile, adică pot fi exprimate printr-o colecție finită de formule care conțin cuvinte și parametri numerici întregi.

Expresiile pentru ecuațiile de mai sus sunt exemple. Dovada inițială a teoremei a fost simplificată considerabil de atunci.

Mărimea reprezentării este mărginită de o funcție care este exponențială în mărimea ecuației. Mai mult, dimensiunea celei mai mici soluții non-banale a ecuației, dacă există, este ea însăși exponențială, iar problema existenței poate fi rezolvată în timp exponențial nedeterminist.

Ecuația Lyndon și Schützenberger

Așa-numita ecuație Lyndon și Schützenberger este ecuația din trei variabile

Xnu=ymzp{\ displaystyle x ^ {n} = y ^ {m} z ^ {p}}

între cuvinte și unde sunt numere întregi. Într-un articol din 1962, Roger C. Lyndon și Marcel-Paul Schützenberger rezolvă această ecuație în cadrul grupului liber . Ele arată că, dacă sunt soluții ale acestei ecuații, ele sunt puteri ale aceluiași element. Ei aduc studiul din grupul liber înapoi la studiul a două ecuații în monoidul liber care implică conjugate de cuvinte. X,y,z{\ displaystyle x, y, z}nu,m,p≥2{\ displaystyle n, m, p \ geq 2}X,y,z{\ displaystyle x, y, z}

Același rezultat este valabil și în monoidul liber (sau mai bine zis în jumătate de grup liber, adică monoidul liber lipsit de cuvântul gol):

Teorema Lyndon-Schützenberger  -  Ecuația din jumătatea liberă are doar soluții ciclice, adică care sunt puteri ale aceluiași cuvânt. Xnu=ymzp{\ displaystyle x ^ {n} = y ^ {m} z ^ {p}}

Au fost date mai multe dovezi directe ale acestei teoreme. Din punct de vedere istoric, primul, după cel al autorilor, este de Danny D. Chu și Hsiang-Sheng Town; Christian Choffrut a dat o dovadă în „Lothaire” în 1997. O dovadă mai scurtă, a lui Tero Harju și Dirk Nowotka, a apărut în 2004, iar alta, mai detaliată de Pál Dömösi și Géza Horváth în 2006. Este prezentată o demonstrație completă. Manualul lui Jeffrey Shallit.

Extensii și generalizări

Extensiile și generalizările au fost date ulterior. André Lentin în 1965 consideră ecuația

Xm=ynuzptq{\ displaystyle x ^ {m} = y ^ {n} z ^ {p} t ^ {q}}

în 4 variabile și se arată, cu condiția ca exponenții să fie cel puțin egali cu 3, că în orice soluție și unul dintre cuvinte sunt puteri ale aceluiași cuvânt. O altă extensie este de la Barbin-Le Rest și Le RestX{\ displaystyle x}y,z,t{\ displaystyle y, z, t}

Kenneth I. Appel și Frans M. Djorup studiază ecuația

z1nuz2nu⋯zknu=ynu{\ displaystyle z_ {1} ^ {n} z_ {2} ^ {n} \ cdots z_ {k} ^ {n} = y ^ {n}},

unde variabilele apar cu același exponent; ele demonstrează în special că soluțiile sunt toate puteri ale aceluiași cuvânt în cazul în care . Tero Harju și Dirk Nowotka în 2005 studiază ecuația mai generală k≤nu{\ displaystyle k \ leq n}

Xk=z1k1z2k2⋯znuknu{\ displaystyle x ^ {k} = z_ {1} ^ {k_ {1}} z_ {2} ^ {k_ {2}} \ cdots z_ {n} ^ {k_ {n}}}.

O variantă a acestor ecuații este considerată de Aleksi Saarela. Acestea sunt ecuațiile formei

Xktu=tu1X1k⋯tunuXnuk{\ displaystyle x ^ {k} u = u_ {1} x_ {1} ^ {k} \ cdots u_ {n} x_ {n} ^ {k}},

evaluat pentru mai multe valori ale exponentului . Arată că, dacă ecuația este valabilă pentru trei valori pozitive ale , atunci este valabilă pentru toate valorile lui . În special, dacă k{\ displaystyle k}k{\ displaystyle k}k{\ displaystyle k}

Xk=X1k⋯Xnuk{\ displaystyle x ^ {k} = x_ {1} ^ {k} \ cdots x_ {n} ^ {k}}

pentru trei valori ale , atunci și sunt puteri ale aceluiași cuvânt. O extensie la monoizi liberi echipată cu un anti- izomorfism involutiv este dată de Manea et. al . Un astfel de morfism este o bijecție a unui monoid liber pe sine care este involutiv ( pentru orice ) și un anti-morfism ( pentru orice ). k{\ displaystyle k}X{\ displaystyle x}Xeu{\ displaystyle x_ {i}} f{\ displaystyle f}f(f(X))=X{\ displaystyle f (f (x)) = x}X{\ displaystyle x}f(Xy)=f(y)f(X){\ displaystyle f (xy) = f (y) f (x)}X,y{\ displaystyle x, y}

Sisteme de ecuații

Un sistem de ecuații este un set de ecuații. Se spune că un sistem este independent dacă nu este echivalent cu niciunul din subsistemele sale. Ehrenfeucht compactitate Teorema afirmă că orice sistem infinit este echivalent cu un subsistem finit, și , prin urmare , un sistem independent nu poate fi infinit.

Mărimea maximă a unui sistem independent de ecuații de cuvinte fără constantă este ușor de determinat în cazul uneia și a două variabile, dar celelalte cazuri rămân deschise, chiar și în cazul a trei variabile, unde răspunsul presupus este de trei. S-a dovedit că dimensiunea maximă a unui sistem independent de ecuații cu trei variabile este de cel mult 18.

Note și referințe

1. Makanin 1977 .
2. Diekert 2002 .
3. Hmelevskii 1976 .
4. Diekert 2015 .
5. Plandowski 2004 .
6. Joi 2013 .
7. Aleksi Saarela, „ Cu privire la complexitatea Teorema Hmelevskii si satisfiabilitate a trei Necunoscut Ecuații“ , în Volker Diekert și Dirk Nowotka (eds), Evoluții în Teoria limbii (Proceedings DLT 2009, Stuttgart) , Springer Verlag, coll.  „Note de curs în informatică” ( nr .  5583),2009( ISBN  978-3-642-02736-9 , DOI  10.1007 / 978-3-642-02737-6_36 ) , p.  443-453.
8. (în) Roger C. Lyndon și Marcel Paul Schützenberger , „  Ecuația într-un grup liberlaM=bNUvs.P{\ displaystyle a ^ {M} = b ^ {N} c ^ {P}}  ” , The Michigan Mathematical Journal , Vol.  9, n o  4,1962, p.  289–298 ( DOI  10.1307 / mmd / 1028998766 , citiți online ).
9. (în) Danny D. Chu și Sheng Hsiang- Town , „  O altă dovadă a teoremei a fost Lyndon și Schützenberger într-un monoid liber  ” , Soochow J. Math. , vol.  4,1978, p.  143-146 ( citește online ).
10. Lothaire, Combinatorics on Words , Cambridge University Press ,1997, Secțiunea 9.2: O ecuație clasică: (Xnuym,zp){\ displaystyle (x ^ {n} y ^ {m}, z ^ {p})}.
11. (în) Tero Harju și Dirk Nowotka , „  Ecuația într-un semigrup liberXeu=yjzk{\ displaystyle x ^ {i} = y ^ {j} z ^ {k}}  ” , Semigroup Forum , vol.  68, nr .  3,2004, p.  488-490 ( Recenzii matematice  2050904 ).
12. (în) Pál Dömösi și Géza Horváth , "  Dovadă alternativă a teoremei Lyndon Schützenberger  " , Informatică teoretică , vol.  366, nr .  3,2006, p.  194–198 ( ISSN  0304-3975 , DOI  10.1016 / j.tcs.2006.08.023 ).
13. (în) Jeffrey Shallit, Un al doilea curs de limbaje formale și teoria automatelor , Cambridge University Press ,2009, 240  p. ( ISBN  978-0-521-86572-2 și 0521865727 ) , Secțiunea 2.3 Teoremele lui Lyndon - Schützenberger.
14. (ro) André Lentin , „  Despre ecuația într-un monoid liberlaM=bNUvs.PdÎ{\ displaystyle a ^ {M} = b ^ {N} c ^ {P} d ^ {Q}}  ” , CR Math. Acad. Știință. Paris , vol.  260, nr .  4,1965, p.  3242–3244 ( Math Reviews  0176949 , citiți online ).
15. Evelyne Barbin-Le Rest și Michel Le Rest , „  Despre combinatoria codurilor cu două cuvinte  ”, Theoretical Computer Science , vol.  41,1985, p.  61–80 ( DOI  10.1016 / 0304-3975 (85) 90060-X ).
16. (în) Kenneth Ira Call și Frans Martin Djorup , „  Pe ecuația într-un semigrup liberz1nuz2nu⋯zknu=ynu{\ displaystyle z_ {1} ^ {n} z_ {2} ^ {n} \ cdots z_ {k} ^ {n} = y ^ {n}}  ” , Trans. Amar. Matematica. Soc. , vol.  134,1968, p.  461–470.
17. (în) Tero Harju și Dirk Nowotka , „  Cu privire la ecuația într-un semigrup liberXk=z1k1z2k2⋯znuknu{\ displaystyle x ^ {k} = z_ {1} ^ {k_ {1}} z_ {2} ^ {k_ {2}} \ cdots z_ {n} ^ {k_ {n}}}  ” , Theoret. Calculator. Știință. , vol.  330, n o  1,2005, p.  117-121.
18. Aleksi Saarela , „  Ecuații de cuvinte cu puteri kth ale variabilelor  ”, Journal of Combinatorial Theory, Seria A , vol.  165,2019, p.  15–31 ( DOI  10.1016 / j.jcta.2019.01.004 ).
19. (în) Florin Manea , Mike Müller , Dirk Nowotka și Shinnosuke Seki , „  Ecuația extinsă a lui Lyndon și Schützenberger  ” , Journal of Computer and System Sciences , vol.  85,2017, p.  132–167 ( DOI  10.1016 / j.jcss.2016.11.003 ).
20. Aleksi Saarela "  Cuvinte despre sisteme independente de ecuații: de la Ehrenfeucht la optsprezece  ", Note de curs în informatică , nr .  11682,2019, p.  60–67 ( ISSN  0302-9743 , DOI  10.1007 / 978-3-030-28796-2_4 )
21. Dirk Nowotka și Aleksi Saarela, „An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consecuences ” , în 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , col.  „Leibniz International Proceedings in Informatics (LIPIcs)” ( nr .  107),2018, 136: 1-136: 13  p. ( DOI  10.4230 / LIPIcs.ICALP.2018.136 , citiți online ).

Bibliografie

• Volker Diekert, „Peste 1700 de ani de ecuații de cuvinte” , în Conference on Algebraic Informatics , Springer, col.  „Note de curs în informatică” ( nr .  9270),2015( ISBN  978-3-319-23020-7 , DOI  10.1007 / 978-3-319-23021-4_2 , arXiv  1507.03215 ) , p.  22-28
• Volker Diekert, cap.  12 „Algoritmul lui Makanin” , în M. Lothaire, Algebraic Combinatorics on Words , Cambridge University Press, col.  "Enciclopedia matematicii și a aplicațiilor sale" ( nr .  90)2002, p.  387-442.
• Youri I. Hmelevskii, Equations in free semigroups , American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (1971),1976, 270  p. ( ISBN  978-0-8218-3007-9 , Math Reviews  0393284 , zbMATH  0326.02032 , prezentare online ) - Tradus din originalul rusesc, publicat în 1971, de GA Kandall.
• Artur Jeż, „ Recompresie : o tehnică simplă și puternică pentru ecuațiile cuvintelor” , în Natacha Portier și Thomas Wilke (eds), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) , col.  „Procedee internaționale de informatică Leibniz (LIPIcs)”,2013( ISBN  978-3-939897-50-7 , DOI  10.4230 / LIPIcs.STACS.2013.233 , citit online ) , p.  233-244
• Gennadiĭ S. Makanin, „ Problema rezolvabilității  ecuațiilor într-un semigrup liber  ”, Soviet Math. Dokl. , vol.  18, n o  21977, p.  330-334- Traducere în engleză a anunțului rezultatului. În rusă: Dokl. Akad. Nauk SSSR 233 (1977), nr. 2, 287–290.
• Gennadiĭ S. Makanin, „ Problema rezolvabilității  ecuațiilor într-un semigrup liber  ”, Math. Sbornik (NS) , voi.  103, n o  21977, p.  147-236, 319 ( Recenzii matematice  0470107 )- Articol complet, în limba rusă. Traducere în engleză: Math. URSS Sbornik 32 (1977)
• Youri Matiassevitch , A zecea problemă a lui Hilbert , Cambridge, Mass., MIT Press ,1993, 288  p. ( ISBN  978-0-262-13295-4 , citit online )
• Youri Matiassevitch , A zecea problemă a lui Hilbert: indecidabilitatea sa , Paris, Masson,1995, 307  p. ( ISBN  2-225-84835-1 ) - Traducere în franceză
• Wojciech Plandowski, „Satisfacția  ecuațiilor de cuvinte cu constante este în PSPACE.  ”, Jurnalul Asociației pentru Mașini de Calculat , vol.  51,2004, p.  483-496 - Versiunea „Jurnal” a comunicării din 1999.
• Wojciech Plandowski , „  Despre generarea PSPACE a unui set de soluții ale ecuației de cuvinte și a aplicațiilor sale  ”, Theoretical Computer Science , vol.  792,2019, p.  20–61 ( DOI  10.1016 / j.tcs.2018.10.023 )

Articole similare

• Combinatorie de cuvinte

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">