Cuvânt fără pătrat

Un cuvânt fără pătrat este un cuvânt în care niciun subcuvânt nu este repetat de 2 ori la rând (adică acest cuvânt nu poate fi reprezentat ca yxxz , unde x , y și z sunt unele subcuvinte).

A. Thue a demonstrat că infinite cuvinte fără pătrate există peste orice alfabet de cel puțin 3 litere. Unul dintre cele mai simple exemple de cuvânt fără pătrat infinit peste un alfabet de 3 litere poate fi construit începând cu un cuvânt și apoi obținerea unui cuvânt din cuvânt folosind substituțiile „a”-> „abcab”, „b”- >"acabcb", "c"- >"acbcacb" . Fiecare cuvânt următor îl va conține pe cel anterior, ceea ce vă permite să construiți un cuvânt infinit „abcabacabcbacbcacbabcabacabcb ...” . $w_{1}=a$ $w_{i}$ $w_{i+1}$

Numărul de cuvinte fără pătrat de trei litere de lungime formează secvența A006156 în OEIS . Crește exponențial de la , iar exponentul este . $n$ $n$ $1.3017...$

Verificarea unui cuvânt pentru dreptate

Dacă există un cuvânt de lungime , atunci putem verifica dacă este fără pătrat pentru acțiuni. Pentru a face acest lucru, trebuie să construiți un arbore de sufix și să faceți calcule preliminare (a se vedea cel mai mic predecesor comun ), permițându-vă să găsiți cel mai mare astfel încât subșirurile de lungime începând de la poziții și , din date , să se potrivească. De asemenea, vom construi un arbore de sufixe și vom efectua calcule pentru șirul invers pentru a găsi lungimea celui mai lung subșir comun care se termină în aceste poziții prin și . $w$ $n$ $O(n\log(n))$ $Pe)$ $O(1)$ $X$ $y$ $l$ $l$ $X$ $y$ $X$ $y$

După aceea, problema este rezolvată recursiv. Să despărțim șirul în mijloc și să verificăm fiecare dintre jumătăți. Dacă unul dintre ele conține un subcuvânt de forma , atunci șirul original nu este nici pătrat liber. Fie poziția începutului celei de-a doua reprize. Pentru toate lungimile , găsiți lungimea subșirului comun pentru pozițiile și , precum și lungimea subșirului comun începând de la pozițiile și , dar mergând în direcția opusă. Dacă , atunci subcuvintele de lungime pornind de la poziții și coincid, ceea ce înseamnă că cuvântul nu este pătrat liber. După aceea, vom face aceeași procedură pentru posturi și pentru toate . Este ușor de observat că, dacă niciuna dintre proceduri nu a găsit un pătrat, atunci poziția nu poate aparține niciunui pătrat, ceea ce înseamnă că cuvântul este fără pătrat. Deoarece, după calcule preliminare, găsirea unui subșir comun se poate face în , algoritmul va avea nevoie de pași pentru a verifica poziția . Ținând cont de recursivitate, obținem complexitatea totală a algoritmului . $xx$ $m$ $1\leq s\leq n$ $l_{1}$ $m$ $m+s$ $l_{2}$ $m$ $m+s$ $l_{1}+l_{2}>s$ $s$ $m-l_{1}+1$ $m+s-l_{1}+1$ $m$ $ms$ $1\leq s\leq n$ $m$ $O(1)$ $m$ $Pe)$ $O(n\log(n))$

Acest algoritm poate fi generalizat cu ușurință pentru a căuta repetări de orice lungime: este suficient să înlocuiți condiția cu o condiție pentru a căuta șiruri care se repetă o dată la rând. $l_{1}+l_{2}>s$ $l_{1}+l_{2}>(k-1)s$ $k$

Dacă în loc de arbori de sufixe folosim matrice de sufixe mai simple și în loc de algoritmul comun de căutare subșiruri folosim un algoritm mai simplu bazat pe rezultate intermediare ale construirii unui tablou de sufixe, atunci acest algoritm va funcționa pentru . Acest lucru nu este cu mult mai rău, având în vedere simplificarea semnificativă a algoritmului în acest caz. $O(1)$ $O(\log(n))$ $O(n\log ^{2}(n))$

Exemple de secvențe infinite fără pătrat

Începând cu „a”, aplică substituții: a -> „abcab”; b -> "acabcb"; c -> "acbcacb" ( A. Thue , 1917)
Începând cu „a”, aplică substituții: a -> „abcbacbcabcba”; b -> "bcacbacabcacb"; c -> „cabacbabcabac” (J. Leech, c.1957)
De asemenea, din secvența Morse-Thue , puteți obține un cuvânt fără pătrat infinit, dacă în această secvență pentru fiecare unitate notați câte zerouri sunt plasate după el la rând. Dacă mai există o unitate după unitate, scriem un . Dacă există un zero, atunci scriem b . Dacă două zerouri, scriem c . Nu pot apărea mai mult de două zerouri la rând. Prin urmare, cuvântul rezultat conține litere de doar trei tipuri. Secvența Morse-Thue începe astfel: 0110100110010110... Deci caracterele inițiale ale cuvântului specificat arată astfel: abcacba ...

Literatură

Allouche, J.-P. și Shallit, J. „Repetiție în cuvinte”. § 1.6 în Secvențe automate: teorie, aplicații, generalizări. Cambridge, Anglia: Cambridge University Press, pp. 14–16, 2003.
Baake, M.; Elser, V.; și Grimm, U. „Entropia cuvintelor fără pătrat”. 8 sept 1998. http://arxiv.org/abs/math-ph/9809010/ .
Bean, D. R.; Ehrenfeucht, A.; și McNulty, G.F. „Modele evitabile în șiruri de simboluri”. Pacific J Math. 85, 261-294, 1979.
Berstel, J. și Reutenauer, C. „Cuvinte fără pătrat și semigrupuri idempotente”. În Combinatorică asupra cuvintelor (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18–38, 1983.
Brandenburg, F.-J. „Creșterea uniformă a homomorfismelor fără putere”. Theor. Calculator. sci. 23, 69-82, 1983.
Brinkhuis, J. „Secvențe non-repetitive pe trei simboluri”. Quart. J Math. Oxford Ser. 2 34, 145-149, 1983.
Crochemore, M. „Caracterizări ascuțite ale morfismelor Squarefree”. Theor. Calculator. Sic. 18, 221-226, 1982.
Crochemore, M. „Tests sur les morphismes faiblement sans carré”. În Combinatorică asupra cuvintelor (Ed. LJ Cummings). Toronto: Academic Press, pp. 63–89, 1983.
Finch, S. R. „Constantele cuvintelor fără modele”. § 5.17 în Constante matematice. Cambridge, Anglia: Cambridge University Press, pp. 367–371, 2003.
Kobayashi, Y. „Cuvinte fără repetiție”. Theor. Calculator. sci. 44, 175-197, 1986.
Leconte, M. „Coduri fără putere”. În Automate on Infinite Words (Ed. M. Nivat și D. Perrin). Berlin: Springer-Verlag, pp. 172-178, 1985.
Noonan, J. și Zeilberger, D. „Metoda Clusterului Goulden-Jackson: extensii, aplicații și implementări”. J. Altfel. Ec. Appl. 5, 355-377, 1999.
Pleasants, PAB „Secvențe nerepetitive”. Proc. Cambridge Philos. soc. 68, 267-274, 1970.
Restivo, A. și Salemi, S. „Cuvinte fără suprapunere pe două simboluri”. În Automate on Infinite Words (Ed. M. Nivat și D. Perrin). New York: Springer-Verlag, pp. 198–206, 1985.
Sloane, NJA Secvențe A006156/M2550 și A051041 în „Enciclopedia on-line a secvențelor întregi”.
Thue, A. „Über unendliche Zeichenreihen”. Norske Vid. Selsk. Skr. Sunt la. Nat. Kl. Christiana 7, 1-22, 1906. Retipărit în Nagell, T.; Selberg, A.; Selberg, S.; și Thalberg, K. (Eds.). Lucrări de matematică alese ale lui Axel Thue. Oslo, Norvegia: Universitetsforlaget, pp. 139-158, 1977.
Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen." Norske Vid. Selsk. Skr. Sunt la. Nat. Kl. Christiana 1, 1-67, 1912. Retipărit în Nagell, T.; Selberg, A.; Selberg, S.; și Thalberg, K. (Eds.). Lucrări de matematică alese ale lui Axel Thue. Oslo, Norvegia: Universitetsforlaget, pp. 413-477, 1977.

Link -uri

Weisstein, Eric W. Squarefree Word (engleză) pe site-ul Wolfram MathWorld .