Exponent critic al unui cuvânt

În matematică și informatică teoretică , în special în combinatorie pe cuvinte , exponentul critic al unui cuvânt (în engleză critic exponent ) este o proprietate a unui cuvânt infinit . Este exponentul celei mai mari puteri fracționare a unui cuvânt care poate apărea în acest cuvânt infinit. Este o măsură a regularității unei serii infinite de simboluri.

Definiție

Fie un cuvânt finit și un număr real. Spunem că un cuvânt este o putere de ordine a dacă , unde este partea întreagă a , este un prefix al și . X{\ displaystyle x}LA{\ displaystyle A}α≥1{\ displaystyle \ alpha \ geq 1}z{\ displaystyle z}α{\ displaystyle \ alpha}X{\ displaystyle x}z=Xnuy{\ displaystyle z = x ^ {n} y}nu{\ displaystyle n}α{\ displaystyle \ alpha}y{\ displaystyle y}X{\ displaystyle x}|z|≥α|X|{\ displaystyle | z | \ geq \ alpha | x |}

Aici sunt cateva exemple.

• Cuvântul este o putere de 3/2 a .lalabblala{\ displaystyle aabbaa}lalabb{\ displaystyle aabb}
• Cuvântul este o putere de 8/5 a .lablalablabla{\ displaystyle abaababa}lablalab{\ displaystyle abaab}
• Un pătrat este o putere de ordinul 2.
• Definiția implică faptul că, dacă un cuvânt este o putere de ordine , este și o putere de ordine pentru toate realele, cu condiția să aibă aceeași parte întreagă.α{\ displaystyle \ alpha}β{\ displaystyle \ beta}β<α{\ displaystyle \ beta <\ alpha}

Acum ia în considerare un cuvânt infinit pe alfabet . Spunem că acest cuvânt are o putere de ordine dacă conține un factor care este o putere de ordine . Se spune că este fără putere de ordine dacă, dimpotrivă, nu conține un factor care este o putere de ordine . De exemplu, un cuvânt fără pătrat este un cuvânt care nu conține un factor pătrat. w{\ displaystyle w}LA{\ displaystyle A} α{\ displaystyle \ alpha}α{\ displaystyle \ alpha} α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}

Exponent critic al este limita de sus a pentru care are puteri de ordinul sau, echivalent, limită inferioară a pentru care nu are nici o putere de ordine . w{\ displaystyle w}α{\ displaystyle \ alpha}w{\ displaystyle w}α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}w{\ displaystyle w}α{\ displaystyle \ alpha}

Exemple

• Exponentul critic al secvenței Prouhet-Thue-Morse este 2. Acest lucru provine din faptul că acest cuvânt conține pătrate, dar nu are un factor exponent strict mai mare de 2, deoarece nu conține un factor de suprapunere, adică de forma unde este prima literă din .XXb{\ displaystyle xxb}b{\ displaystyle b}X{\ displaystyle x}
• Exponentul critic al cuvântului Fibonacci infinit este . Infinit Cuvântul lui Fibonacci conține cuburi, și este fără curent 4 - lea . Conține, pentru , în factor cuvintele formei(5+5)/2{\ displaystyle (5 + {\ sqrt {5}}) / 2}
  nu≥4{\ displaystyle n \ geq 4}fnufnufnugnu-1{\ displaystyle f_ {n} f_ {n} f_ {n} g_ {n-1}},unde este un cuvânt Fibonacci finit și unde este cuvântul privat al ultimelor sale două litere. Cel mai simplu dintre aceste cuvinte este (01001) (01001) (01001) 0. Lungimea acestor cuvinte este , în cazul în care este mii numărul Fibonacci , iar exponentul acestor cuvinte estefnu{\ displaystyle f_ {n}}gnu-1{\ displaystyle g_ {n-1}}fnu-1{\ displaystyle f_ {n-1}}3Fnu+(Fnu-1-2){\ displaystyle 3F_ {n} + (F_ {n-1} -2)}Fnu{\ displaystyle F_ {n}}nu{\ displaystyle n}3+(Fnu-1-2)/Fnu{\ displaystyle 3+ (F_ {n-1} -2) / F_ ​​{n}}.
• Cele Cuvintele sturmian au fost toate mai mari decât exponenții critice Fibonacci de cuvinte.
• Cuvântul Champernowne conține toți factorii, astfel încât toate puterile. Exponentul său critic este infinit.

cometariu

Primele două exemple arată cele două cazuri care pot apărea pentru exponentul critic: în cuvântul lui Thue-Morse, exponentul critic este exponentul unei puteri realizate și, prin urmare, intervalul exponenților factorilor care nu sunt puterea este deschis. De aceea spunem, de asemenea, că cuvântul lui Thue-Morse este fără putere , simbolul aditiv însemnând că este fără putere strict mai mare decât 2. 2+{\ displaystyle 2 ^ {+}}

Pentru cuvântul Fibonacci, pe de altă parte, este deschis intervalul exponenților puterilor realizate. Este neputincios , iar acest exponent fiind irațional, desigur că nu poate fi realizat. (5+5)/2{\ displaystyle (5 + {\ sqrt {5}}) / 2}

Proprietăți

Proprietăți notabile ale exponentului critic:

• Exponentul critic poate lua orice valoare reală mai mare decât1{\ displaystyle 1} .
• Exponentul critic al unui cuvânt morfic peste un alfabet finit este un număr algebric al cărui grad este cel mult egal cu dimensiunea alfabetului .
• Exponentul critic al unui cuvânt sturmian este finit dacă și numai dacă coeficienții expansiunii fracției continue a pantei sale sunt delimitați.

Articole similare

• Exponent critic al unui sistem fizic
• Cuvânt sturmian
• Cuvânt automat
• Cuvânt morfic
• Cuvânt cvasi-periodic

Note și referințe

Note

1. Utilizarea termenului exponent critic a fost sistematizată în ( Krieger 2006 ). Apare înainte în ( Vandeth 2000 ). Cuvântul index a fost de asemenea folosit , de exemplu în ( Allouche și Shallit 2003 ) sau ( Damanik și Lenz 2003 ).
2. Allouche și Shallit 2003 .
3. Mignosi și Pirillo 1992 .
4. Damanik și Lenz 2003 .
5. Krieger și Shallit 2007 .
6. Krieger 2006 .
7. Acest rezultat, de la ( Mignosi 1991 ), a fost apoi clarificat. Cunoaștem exact exponenții critici ai cuvintelor sturmiene de atunci ( Carpi și De Luca 2000 ) și ( Vandeth 2000 ).

(fr) Acest articol este preluat parțial sau în întregime din articolul din Wikipedia în engleză intitulat „  Exponent critic al unui cuvânt  ” ( vezi lista autorilor ) .

Referințe

• (en) Jean-Paul Allouche și Jeffrey O. Shallit , Secvențe automate: teorie, aplicații, generalizări , Cambridge, Cambridge University Press,2003, 571  p. ( ISBN  0-521-82332-3 , Math Reviews  1997038 , zbMATH  1086.11015 )
• Dalia Krieger , „Despre exponenți critici în puncte fixe de morfisme care nu se șterg” , în Oscar H. Ibarra și Zhe Dang, Developments in Language Theory: Proceedings 10th International Conference, DLT 2006 , Springer-Verlag, col.  „Note de curs în informatică” ( nr .  4036)2006, p.  280–291
• Dalia Krieger și J. Shallit , „  Fiecare număr real mai mare decât unul este un exponent critic  ”, Theor. Calculator. Știință. , vol.  381,2007, p.  177–182 ( DOI  10.1016 / j.tcs.2007.04.037 )
• M. Lothaire , Algebraic combinatorics on words , Reprint of the 2002 Cambridge University Press edition , col.  "Enciclopedia matematicii și a aplicațiilor sale" ( nr .  90)2011, 520  p. ( ISBN  978-0-521-18071-9 , Math Reviews  1905123 , zbMATH  1221.68183 , prezentare online )
• Filippo Mignosi și Guiseppe Pirillo , „  Repetiții în cuvântul infinit Fibonacci  ”, Teoretic. Informa. Aplic. , vol.  26, n o  3,1992, p.  199–204
• D. Damanik și D. Lenz , „  Puteri în secvențe sturmiene  ”, European Journal of Combinatorics , vol.  24, nr .  4,2003, p.  377–390
• Filippo Mignosi , „  Despre numărul de factori ai cuvintelor sturmiene  ”, Teorie. Calculator. Sci , vol.  82,1991, p.  71-84
• Arturo Carpi și Aldo de Luca , „  Factori speciali, periodicitate și o aplicație la cuvintele sturmiene  ”, Acta Informatica , vol.  36,2000, p.  983-1006
• D. Vandeth , „  Cuvinte sturmiene și cuvinte cu un exponent critic  ”, Teoretic. Calculator. Știință. , vol.  242,2000, p.  283-300

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