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

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

Бесквадра́тное сло́во (англ. 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.
  • Также из последовательности Морса-Туэ можно получить бесконечное бесквадратное слово, если в этой последовательности для каждой единицы отметить, сколько нулей размещено после неё подряд. Если после единицы стоит ещё одна единица, пишем a. Если стоит один ноль, то пишем b. Если два нуля, пишем c. Больше двух нулей подряд встретиться не может. Поэтому полученное слово содержит буквы только трёх видов. Последовательность Морса-Туэ начинается следующим образом: 0110100110010110... Значит, начальные символы указанного слова выглядят так: abcacba...

Литература[править | править вики-текст]

  • 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.

Ссылки[править | править вики-текст]