Négyzet nélküli szó

A négyzet nélküli szó olyan szó , amelyben egyetlen részszó sem ismétlődik 2-szer egymás után (vagyis ez a szó nem ábrázolható yxxz -ként , ahol x , y és z néhány részszó).

A. Thu bebizonyította, hogy végtelen négyzet nélküli szavak léteznek bármely legalább 3 betűből álló ábécé felett. Az egyik legegyszerűbb példa egy végtelen négyzet nélküli szóra egy 3 betűből álló ábécé fölött úgy szerkeszthető, hogy egy szóval kezdjük , majd az "a"->"abcab", "b"- helyettesítések segítségével szót kapunk a szóból . >"acabcb", "c"- >"acbcacb" . Minden következő szó tartalmazza az előzőt, ami lehetővé teszi egy végtelen "abcabacabcbacbcacbabcabacabcb ..." szó felépítését . $w_{1}=a$ $w_{i}$ $w_{i+1}$

A három betűből álló négyzet nélküli szavak száma az A006156 sorozatot alkotja az OEIS- ben . Exponenciálisan növekszik -tól , a kitevő pedig . $n$ $n$ $1.3017...$

Egy szó négyszögletességének ellenőrzése

Ha van hosszú szó , akkor ellenőrizhetjük, hogy négyzetmentes-e a cselekvésekre. Ehhez létre kell hoznia egy utótagfát, és előzetes számításokat kell végeznie (lásd a legkisebb közös elődöt ), amely lehetővé teszi a legnagyobb megtalálását úgy, hogy a pozíciókból és az adatokból kiinduló hosszúságú részkarakterláncok illeszkedjenek. Egy utótagfát is készítünk, és számításokat végzünk a fordított karakterláncra, hogy megtudjuk a leghosszabb közös részkarakterlánc hosszát, amely ezekben a pozíciókban és -vel végződik. $w$ $n$ $O(n\log(n))$ $Tovább)$ $O(1)$ $x$ $y$ $l$ $l$ $x$ $y$ $x$ $y$

Ezt követően a probléma rekurzív módon megoldódik. Osszuk ketté a zsinórt középen, és nézzük meg mindegyik felét. Ha ezek egyike a formájú részszót tartalmazza, akkor az eredeti karakterlánc sem négyzetmentes. Legyen a második félidő elejének helyzete. Minden hosszúság esetén keresse meg a és pozíciók közös részkarakterláncának hosszát, valamint a és pozíciókból induló , de az ellenkező irányba haladó közös részkarakterlánc hosszát. Ha , akkor a pozíciókból induló és hosszúságú részszavak egybeesnek, ami azt jelenti, hogy a szó nem négyzetmentes. Ezt követően ugyanazt az eljárást hajtjuk végre a pozíciókra és mindenre . Könnyen belátható, hogy ha egyik eljárás sem talált négyzetet, akkor a pozíció nem tartozhat egyik négyzethez sem, ami azt jelenti, hogy a szó négyzet nélküli. Mivel az előzetes számítások után a közös részkarakterlánc keresése megoldható a -ban , az algoritmusnak lépésekre lesz szüksége a pozíció ellenőrzéséhez . A rekurziót figyelembe véve megkapjuk az algoritmus teljes komplexitását . $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$ $Tovább)$ $O(n\log(n))$

Ez az algoritmus könnyen általánosítható tetszőleges hosszúságú ismétlődések keresésére: elegendő a feltételt egy feltételre cserélni, hogy olyan karakterláncokat keressünk, amelyek egymás után egyszer ismétlődnek. $l_{1}+l_{2}>s$ $l_{1}+l_{2}>(k-1)s$ $k$

Ha az utótagfák helyett egyszerűbb utótag tömböket használunk , és a gyakori részstring keresési algoritmus helyett egy egyszerűbb , utótagtömb felépítésének köztes eredményein alapuló algoritmust, akkor ez az algoritmus fog működni . Ez nem sokkal rosszabb, tekintettel az algoritmus jelentős egyszerűsítésére ebben az esetben. $O(1)$ $O(\log(n))$ $O(n\log ^{2}(n))$

Példák négyzet nélküli végtelen sorozatokra

Az "a" betűvel kezdődően alkalmazza a helyettesítéseket: a -> "abcab"; b -> "acabcb"; c -> "acbcacb" ( A. Thue , 1917)
Az "a" betűvel kezdődően alkalmazzon helyettesítéseket: a -> "abcbacbcabcba"; b -> "bcacbacabcacb"; c -> "cabacbabcabac" (J. Leech, 1957 körül)
A Morse- Csú sorozatból is kaphat egy végtelen négyzet nélküli szót, ha ebben a sorozatban minden egységhez megjegyzi, hogy hány nulla kerül utána egy sorban. Ha az egység után még egy egység van, akkor írunk egy -ot . Ha egy nulla van, akkor b -t írunk . Ha két nulla, akkor c -t írunk . Egymás után kettőnél több nulla nem fordulhat elő. Ezért az eredményül kapott szó csak háromféle betűt tartalmaz. A Morse-Thue sorozat így kezdődik: 0110100110010110... Tehát a megadott szó kezdő karakterei így néznek ki: abcacba ...

Irodalom

Allouche, J.-P. és Shallit, J. "Ismétlés szavakban". 1.6. § Automatikus sorozatok: elmélet, alkalmazások, általánosítások. Cambridge, Anglia: Cambridge University Press, pp. 2003. 14–16.
Baake, M.; Elser, V.; és Grimm, U. "The Entropy of Square-Free Words". 1998. szeptember 8. http://arxiv.org/abs/math-ph/9809010/ .
Bean, D. R.; Ehrenfeucht, A.; és McNulty, G. F. "Avoidable Patterns in Strings of Symbols". Pacific J Math. 85, 261-294, 1979.
Berstel, J. és Reutenauer, C. "Square-Free Words and Idempotent Semigroups." In Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 1983. 18–38.
Brandenburg, F.-J. "Egységesen növekvő hatalommentes homomorfizmusok." Theor. Comput. sci. 23, 69-82, 1983.
Brinkhuis, J. "Nem ismétlődő szekvenciák három szimbólumon." Kvart. J Math. Oxford Ser. 2 34, 145-149, 1983.
Crochemore, M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput. Sic. 18, 221-226, 1982.
Crochemore, M. "Tests sur les morphismes faiblement sans carré." In Combinatorics on Words (szerk. LJ Cummings). Toronto: Academic Press, pp. 63–89, 1983.
Finch, S. R. "Mintamentes szókonstansok". § 5.17 a Matematikai állandóknál. Cambridge, Anglia: Cambridge University Press, pp. 367–371, 2003.
Kobayashi, Y. "Ismétlésmentes szavak". Theor. Comput. sci. 44, 175-197, 1986.
Leconte, M. "th Power-Free Codes". In Automata on Infinite Words (szerk. M. Nivat és D. Perrin). Berlin: Springer-Verlag, pp. 172-178, 1985.
Noonan, J. és Zeilberger, D. "A Goulden-Jackson Cluster Method: Extensions, Applications and Implementations." J. Különböző. Equ. Appl. 5, 355-377, 1999.
Pleasants, PAB "Nonrepetitive Sequences". Proc. Cambridge Philos. szoc. 68, 267-274, 1970.
Restivo, A. és Salemi, S. "Overlap-Free Words on Two Symbols." In Automata on Infinite Words (szerk. M. Nivat és D. Perrin). New York: Springer-Verlag, pp. 1985, 198–206.
Sloane, NJA Sequences A006156/M2550 és A051041 in "The On-Line Encyclopedia of Integer Sequences".
Thue, A. "Über unendliche Zeichenreihen." Norske Vid. Selsk. Skr. Én, Mat. Nat. Kl. Christiana 7, 1-22, 1906. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; és Thalberg, K. (szerk.). Axel Thue válogatott matematikai dolgozatai. Oslo, Norvégia: Universitetsforlaget, pp. 139-158, 1977.
Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen." Norske Vid. Selsk. Skr. Én, Mat. Nat. Kl. Christiana 1, 1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; és Thalberg, K. (szerk.). Axel Thue válogatott matematikai dolgozatai. Oslo, Norvégia: Universitetsforlaget, pp. 413-477, 1977.

Linkek

Weisstein, Eric W. Squarefree Word (angol) a Wolfram MathWorld webhelyén .