Firkantløst ord

Et firkantfrit ord er et ord , hvor intet underord gentages 2 gange i træk (det vil sige, at dette ord ikke kan repræsenteres som yxxz , hvor x , y og z er nogle underord).

A. Thue beviste, at uendelige firkantede frie ord eksisterer over ethvert alfabet på mindst 3 bogstaver. Et af de enkleste eksempler på et uendeligt firkant-frit ord over et alfabet på 3 bogstaver kan konstrueres ved at starte med et ord og derefter få et ord fra ordet ved at bruge substitutionerne "a"->"abcab", "b"- >"acabcb", "c"- >"acbcacb" . Hvert næste ord vil indeholde det forrige, hvilket giver dig mulighed for at bygge et uendeligt ord "abcabacabcbacbcacbabcabacabcb ..." . $w_{1}=a$ $w_{i}$ $w_{i+1}$

Antallet af kvadratfrie ord med tre længdebogstaver danner sekvensen A006156 i OEIS . Den vokser eksponentielt fra , og eksponenten er . $n$ $n$ $1.3017...$

Kontrol af et ord for kvadratisk

Hvis der er et ord af længde , så kan vi tjekke, om det er firkantfrit for handlinger. For at gøre dette skal du bygge et suffikstræ og foretage foreløbige beregninger (se den mindste almindelige forgænger ), så du kan finde den største , således at delstrenge med længde startende fra positioner og ud fra data matcher. Vi vil også bygge et suffikstræ og udføre beregninger for den omvendte streng for at finde længden af den længste fælles understreng, der ender i disse positioner med og . $w$ $n$ $O(n\log(n))$ $På)$ $O(1)$ $x$ $y$ $l$ $l$ $x$ $y$ $x$ $y$

Herefter løses problemet rekursivt. Lad os flække snoren på midten og tjekke hver af halvdelene. Hvis en af dem indeholder et underord af formen , så er den oprindelige streng heller ikke firkantfri. Lad være positionen i begyndelsen af anden halvleg. For alle længder skal du finde længden af den fælles understreng for positioner og , samt længden af den fælles understreng, der starter ved positioner og , men går i den modsatte retning. Hvis , så falder underordene med længde , der starter fra positionerne og sammen, hvilket betyder, at ordet ikke er firkantfrit. Derefter vil vi gøre den samme procedure for stillinger og for alle . Det er let at se, at hvis ingen af procedurerne fandt en firkant, så kan positionen ikke tilhøre nogen firkant, hvilket betyder, at ordet er firkantløst. Da man efter foreløbige beregninger kan finde en fælles understreng i , vil algoritmen have brug for trin for at kontrollere positionen . Under hensyntagen til rekursion opnår vi den samlede kompleksitet af algoritmen . $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$ $På)$ $O(n\log(n))$

Denne algoritme kan let generaliseres til at søge efter gentagelser af enhver længde: det er nok at erstatte betingelsen med en betingelse for at søge efter strenge, der gentages én gang i træk. $l_{1}+l_{2}>s$ $l_{1}+l_{2}>(k-1)s$ $k$

Hvis vi i stedet for suffikstræer bruger simplere suffiksarrays og i stedet for den almindelige substring-søgealgoritme bruger vi en enklere algoritme baseret på mellemresultater ved at konstruere et suffiksarray, så vil denne algoritme fungere for . Dette er ikke meget værre i betragtning af den betydelige forenkling af algoritmen i dette tilfælde. $O(1)$ $O(\log(n))$ $O(n\log ^{2}(n))$

Eksempler på firkantfri uendelige sekvenser

Start med "a", anvend erstatninger: a -> "abcab"; b -> "acabcb"; c -> "acbcacb" ( A. Thue , 1917)
Start med "a", anvend erstatninger: a -> "abcbacbcabcba"; b -> "bcacbacabcacb"; c -> "cabacbabcabac" (J. Leech, ca. 1957)
Også fra Morse-Thue-sekvensen kan du få et uendeligt kvadratløst ord, hvis du i denne rækkefølge for hver enhed noterer, hvor mange nuller der er placeret efter det i en række. Hvis der er en enhed mere efter enheden, skriver vi en . Hvis der er et nul, så skriver vi b . Hvis to nuller, skriver vi c . Mere end to nuller i træk kan ikke forekomme. Derfor indeholder det resulterende ord kun bogstaver af tre typer. Morse-Thue-sekvensen begynder således: 0110100110010110... Så de indledende tegn i det angivne ord ser sådan ud: abcacba ...

Litteratur

Allouche, J.-P. og Shallit, J. "Gentagelse i ord." § 1.6 i Automatiske sekvenser: Teori, applikationer, generaliseringer. Cambridge, England: Cambridge University Press, s. 14-16, 2003.
Baake, M.; Elser, V.; og Grimm, U. "The Entropy of Square-Free Words." 8. september 1998. http://arxiv.org/abs/math-ph/9809010/ .
Bean, D.R.; Ehrenfeucht, A.; og McNulty, G.F. "Avoidable Patterns in Strings of Symbols." Pacific J Math. 85, 261-294, 1979.
Berstel, J. og Reutenauer, C. "Square-Free Words and Idempotent Semigroups." I Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18-38, 1983.
Brandenburg, F.-J. "Ensartet voksende magtfrie homomorfismer." Theor. Comput. sci. 23, 69-82, 1983.
Brinkhuis, J. "Ikke-gentagende sekvenser på tre symboler." Quart. J Math. Oxford Ser. 2 34, 145-149, 1983.
Crochemore, M. "Skarpe karakteriseringer af kvadratfrie morfismer." Theor. Comput. Sic. 18, 221-226, 1982.
Crochemore, M. "Tests sur les morphismes faiblement sans carré." I Combinatorics on Words (red. LJ Cummings). Toronto: Academic Press, pp. 63-89, 1983.
Finch, S. R. "Mønsterfrie ordkonstanter." § 5.17 i Matematiske konstanter. Cambridge, England: Cambridge University Press, s. 367-371, 2003.
Kobayashi, Y. "Gentagelsesfrie ord." Theor. Comput. sci. 44, 175-197, 1986.
Leconte, M. "th Power-Free Codes." I Automata on Infinite Words (Ed. M. Nivat og D. Perrin). Berlin: Springer-Verlag, s. 172-178, 1985.
Noonan, J. og Zeilberger, D. "The Goulden-Jackson Cluster Method: Extensions, Applications and Implementations." J. Forskellige. Equ. Appl. 5, 355-377, 1999.
Pleasants, PAB "Non-repetitive Sequences." Proc. Cambridge Philos. soc. 68, 267-274, 1970.
Restivo, A. og Salemi, S. "Overlapningsfrie ord på to symboler." I Automata on Infinite Words (Ed. M. Nivat og D. Perrin). New York: Springer-Verlag, pp. 198-206, 1985.
Sloane, NJA Sequences A006156/M2550 og A051041 i "The On-Line Encyclopedia of Integer Sequences."
Thue, A. "Über unendliche Zeichenreihen." Norske Vid. Selsk. Skr. Jeg er ved. Nat. Kl. Christiana 7, 1-22, 1906. Genoptrykt i Nagell, T.; Selberg, A.; Selberg, S.; og Thalberg, K. (red.). Udvalgte matematiske papirer af Axel Thue. Oslo, Norge: Universitetsforlaget, pp. 139-158, 1977.
Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen." Norske Vid. Selsk. Skr. Jeg er ved. Nat. Kl. Christiana 1, 1-67, 1912. Genoptrykt i Nagell, T.; Selberg, A.; Selberg, S.; og Thalberg, K. (red.). Udvalgte matematiske papirer af Axel Thue. Oslo, Norge: Universitetsforlaget, pp. 413-477, 1977.

Firkantløst ord

Kontrol af et ord for kvadratisk

Eksempler på firkantfri uendelige sekvenser

Litteratur

Links