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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Бесквадра́тное сло́во (англ. 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.

Ссылки[править | править исходный текст]