Бесквадратное слово

Бесквадра́тное сло́во (англ. squarefree word) — слово, в котором никакое подслово не повторяется подряд 2 раза (т.е. это слово нельзя представить в виде yxxz, где x, у и z — некоторые подслова).

А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова $w_1=a$ и далее из слова $w_i$ получать слово $w_{i+1}$ с помощью замен «a»->«abcab», «b»->«acabcb», «c»->«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово «abcabacabcbacbcacbabcabacabcb…». Число бесквадратных слов длины $n$ растет экспоненциально от $n$. Показатель экспоненты $s$ на данный момент оценивается как $1.109999\dots=65^{1/40}<s<8416550317984^{1/108}=1.317227\dots$([1]).

Проверка слова на бесквадратность

Если есть слово $w$ длины $n$, то можно проверить является ли оно бесквадратным за $O(n\log(n))$ действий. Для этого нужно построить за $O(n)$ суффиксное дерево и сделать предварительные расчеты (см. наименьший общий предшественник), позволяющие за $O(1)$ находить по данным $x$ и $y$ наибольшее $l$ такое, что подстроки длины $l$ начинающиеся с позиций $x$ и $y$ совпадают. Также построим суффиксное дерево и выполним этим расчеты для обратной строки, чтобы по $x$ и $y$ находить длину наибольшей общей подстроки, заканчивающуюся в этих позициях.

После этого задача решается рекурсивно. Разобъем строку посередине и проверим каждую из половинок. Если в одной из них есть подслово вида $xx$, то и исходная строка не является бесквадратной. Пусть $m$ — позиция начала второй половинки. Для всех длин $1\le s\le 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$ и $m-s$ для всех $1\le s\le n$. Легко видеть, что если ни одна из процедур не нашла квадрата, то и позиция $m$ не может принадлежать никакому квадрату, а значит слово является бесквадратным. Поскольку после предварительных расчетов нахождение общей подстроки можно выполнить за $O(1)$, то для проверки позиции $m$ алгоритму понадобиться $O(n)$ шагов. С учётом рекурсии получаем общую сложность алгоритма $O(n\log(n))$.

Этот алгоритм легко обобщается на поиски повторений любой длины: достаточно заменить условие $l_1+l_2>s$ на условие $l_1+l_2>(k-1)s$ для поиска строк, повторяющихся $k$ раз подряд.

Если вместо суффиксных деревьев использовать более простые суффиксные массивы и вместо алгоритма поиска общей подстроки за $O(1)$ использовать более простой алгоритм за $O(\log(n))$ на основе промежуточных результатов построения суффиксного массива, то этот алгоритм будет работать за $O(n\log^2(n))$. Это не сильно хуже, учитывая значительное упрощение алгоритма в этом случае.

Примеры бесквадратных бесконечных последовательностей

• Начиная с «а» применять замены: a -> «abcab»; b -> «acabcb»; c -> «acbcacb» (А. Туэ, 1917)
• Начиная с «а» применять замены: a -> «abcbacbcabcba»; b -> «bcacbacabcacb»; c -> «cabacbabcabac» (J. Leech, c.1957)
• Последовательность Морса-Туэ, если её разделить на группы по 2 цифры и каждую группу заменить соответствующим образом: 01 -> a, 10 -> b, 00 -> c, 11 -> c.

Литература

• Allouche, J.-P. and Shallit, J. «Repetition in Words.» § 1.6 in Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 14–16, 2003.
• Baake, M.; Elser, V.; and Grimm, U. «The Entropy of Square-Free Words.» 8 Sep 1998. http://arxiv.org/abs/math-ph/9809010/.
• Bean, D. R.; Ehrenfeucht, A.; and McNulty, G. F. «Avoidable Patterns in Strings of Symbols.» Pacific J. Math. 85, 261—294, 1979.
• Berstel, J. and Reutenauer, C. «Square-Free Words and Idempotent Semigroups.» In Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18–38, 1983.
• Brandenburg, F.-J. «Uniformly Growing th Power-Free Homomorphisms.» Theor. Comput. Sci. 23, 69-82, 1983.
• Brinkhuis, J. «Non-Repetitive Sequences on Three Symbols.» Quart. 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 (Ed. L. J. Cummings). Toronto: Academic Press, pp. 63–89, 1983.
• Finch, S. R. «Pattern-Free Word Constants.» § 5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367–371, 2003.
• Kobayashi, Y. «Repetition-Free Words.» Theor. Comput. Sci. 44, 175—197, 1986.
• Leconte, M. «th Power-Free Codes.» In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). Berlin: Springer-Verlag, pp. 172–178, 1985.
• Noonan, J. and Zeilberger, D. «The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations.» J. Differ. Eq. Appl. 5, 355—377, 1999.
• Pleasants, P. A. B. «Nonrepetitive Sequences.» Proc. Cambridge Philos. Soc. 68, 267—274, 1970.
• Restivo, A. and Salemi, S. «Overlap-Free Words on Two Symbols.» In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). New York: Springer-Verlag, pp. 198–206, 1985.
• Sloane, N. J. A. Sequences A006156/M2550 and A051041 in «The On-Line Encyclopedia of Integer Sequences.»
• Thue, A. «Über unendliche Zeichenreihen.» Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7, 1-22, 1906. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 139–158, 1977.
• Thue, A. «Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.» Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 1, 1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 413–477, 1977.

Ссылки

• Weisstein, Eric W. Squarefree Word (англ.) на сайте Wolfram MathWorld.