Слово без квадратов - Square-free word

В комбинаторика, а свободное слово это слово (последовательность символов), не содержащая квадратов. А квадрат это слово формы XX, куда Икс не пусто. Таким образом, слово без квадратов также можно определить как слово, которое избегает шаблона XX.

Конечные бесквадратные слова

Двоичный алфавит

Над двоичным алфавит ${displaystyle {0,1}}$, единственные бесквадратные слова - это пустое слово ${displaystyle epsilon ,0,1,01,10,010}$, и ${displaystyle 101}$.

Троичный алфавит

Над троичным алфавитом ${displaystyle {0,1,2}}$, бесквадратных слов бесконечно много. Можно посчитать количество ${displaystyle c(n)}$ слов без квадратов длины п.

Количество троичных бесквадратных слов длины n^[1]

п	0	1	2	3	4	5	6	7	8	9	10	11	12
${displaystyle c(n)}$	1	3	6	12	18	30	42	60	78	108	144	204	264

Это число ограничено ${displaystyle c(n)=Theta (alpha ^{n})}$, куда ${ extstyle 1.3017597<alpha <1.3017619}$^[2]. Верхняя граница ${displaystyle alpha }$ можно найти через Лемма Фекете и приближение автоматы. Нижнюю границу можно найти, найдя замену, сохраняющую свободу от квадратов^[2].

Алфавит с более чем тремя буквами

Поскольку существует бесконечно много бесквадратных слов в трехбуквенном алфавите, это означает, что существует также бесконечно много бесквадратных слов в алфавите из более чем трех букв.

В следующей таблице показана точная скорость роста k-арочные бесквадратные слова:

Скорость роста k-арно-квадратные слова^[2]

размер алфавита (k)	4	5	6	7	8	9
скорость роста	2.6215080	3.7325386	4.7914069	5.8284661	6.8541173	7.8729902
размер алфавита (k)	10	11	12	13	14	15
скорость роста	8.8874856	9.8989813	10.9083279	11.9160804	12.9226167	13.9282035

Двумерные слова

Рассмотрим карту ${displaystyle { extbf {w}}}$ из ${displaystyle mathbb {N} ^{2}}$ к А, куда А это алфавит и ${displaystyle { extbf {w}}}$ называется двумерным словом. Позволять ${displaystyle w_{m,n}}$ быть входом ${displaystyle { extbf {w}}(m,n)}$. Слово ${displaystyle { extbf {x}}}$ это линия ${displaystyle { extbf {w}}}$ если существует ${displaystyle i_{1},i_{2},j_{1},j_{2}}$такой, что ${displaystyle { ext{gcd}}(j_{1},j_{2})=1}$, и для ${displaystyle tgeq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}}$^[3].

Карпи^[4] доказывает, что существует двумерное слово ${displaystyle { extbf {w}}}$ над 16-буквенным алфавитом таким образом, чтобы каждая строка ${displaystyle { extbf {w}}}$ не содержит квадратов. Компьютерный поиск показывает, что нет двухмерных слов ${displaystyle { extbf {w}}}$над 7-буквенным алфавитом, так что каждая строка ${displaystyle { extbf {w}}}$ без квадратов.

Генерация конечных бесквадратных слов

Шур^[5] предлагает алгоритм, называемый R2F (random-t (w) o-free), который может генерировать бесквадратное слово длины п над любым алфавитом из трех и более букв. Этот алгоритм основан на модификации сжатие энтропии: он случайным образом выбирает буквы из k-буквенного алфавита для создания ${displaystyle (k+1)}$-арное бесквадратное слово.

алгоритм R2F является    Вход: размер алфавита ${displaystyle kgeq 2}$,           длина слова ${displaystyle n>1}$    выход: а ${displaystyle (k+1)}$-арное слово без квадратов шдлины п.    (Обратите внимание, что ${ extstyle color {gray}Sigma _{k+1}}$ это алфавит с буквами ${displaystyle color {gray}{1,...,k+1}}$.) (На слово ${displaystyle color {gray}win Sigma _{k}}$, ${displaystyle color {gray}chi _{w}}$ это перестановка ${displaystyle color {gray}Sigma _{k}}$ такой, что а предшествует б в ${displaystyle color {gray}chi _{w}}$ если самая правая позиция а в ш находится справа от крайней правой позиции б в ш. Например, ${displaystyle color {gray}w=136263163in Sigma _{6}}$ имеет ${displaystyle color {gray}chi _{w}=361245}$.)    выберите ${displaystyle w[1]}$ в ${ extstyle Sigma _{k+1}}$ равномерно случайно набор ${displaystyle chi _{w}}$ к ${displaystyle w[1]}$ за которыми следуют все остальные буквы ${ extstyle Sigma _{k+1}}$ в порядке возрастания набор номер N итераций к 0    пока ${displaystyle |w|<n}$ делать        выберите j в ${ extstyle Sigma _{k}}$ равномерно случайным образом добавить ${displaystyle a=chi _{w}[j+1]}$ до конца ш        Обновить ${displaystyle chi _{w}}$ смещение первого j элементы справа и установка ${displaystyle chi _{w}[1]=a}$        приращение N к 1        если ш заканчивается квадратом ранга р тогда            удалить последний р письма ш    возвращаться ш

Каждое (k + 1) -арное бесквадратное слово может быть выходом алгоритма R2F, потому что на каждой итерации оно может добавлять любую букву, кроме последней буквы ш.

Ожидаемое количество случайных k-арных букв, используемых алгоритмом R2F для построения ${displaystyle (k+1)}$-арное слово без квадратов длины п является

$${displaystyle N=nleft(1+{frac {2}{k^{2}}}+{frac {1}{k^{3}}}+{frac {4}{k^{4}}}+Oleft({frac {1}{k^{5}}}ight)ight)+O(1).}$$

Обратите внимание, что существует алгоритм, который может проверить квадратность слова длиной п в ${displaystyle O(nlog n)}$ время. Апостолико и Препарата^[6] дать алгоритм, использующий суффиксные деревья. Crochemore^[7] использует разбиение в своем алгоритме. Майн и Лоренц^[8] предоставить алгоритм, основанный на методе «разделяй и властвуй». Наивная реализация может потребовать ${displaystyle O(n^{2})}$ время проверить квадратность слова длины п.

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

В любом языке существуют сколь угодно длинные бесквадратные слова. алфавит с тремя или более буквами, как доказано Аксель Туэ^[9].

Примеры

Первое отличие Последовательность Туэ – Морса

Одним из примеров бесконечного бесквадратного слова над алфавитом размера 3 является слово над алфавитом ${displaystyle {-1,0,+1}}$ полученный путем взятия первое отличие из Последовательность Туэ – Морса ^[9]. То есть из последовательности Туэ – Морса

${displaystyle 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...}$

один образует новую последовательность, в которой каждый член является разностью двух последовательных членов последовательности Туэ – Морса. В результате получается бесквадратное слово

${displaystyle 1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...}$(последовательность A029883 в OEIS ).

Пиявка с морфизм

Другой пример, найденный Джон Лич^[10] определяется рекурсивно над алфавитом ${displaystyle {0,1,2}}$. Позволять ${displaystyle w_{1}}$ любое слово без квадратов, начинающееся с буквы 0. Определите слова ${displaystyle {w_{i}mid iin mathbb {N} }}$ рекурсивно следующим образом: слово ${displaystyle w_{i+1}}$ получается из ${displaystyle w_{i}}$ путем замены каждого 0 в ${displaystyle w_{i}}$ с 0121021201210, каждый 1 с 1202102012021, и каждый 2 с 2010210120102. Можно доказать, что последовательность сходится к бесконечному бесквадратному слову

0121021201210120210201202120102101201021202102012021...

Генерация бесконечных слов без квадратов

Бесконечные бесквадратные слова могут быть созданы с помощью бесквадратный морфизм. Морфизм называется бесквадратным, если образ каждого бесквадратного слова бесквадратный. Морфизм называется k-бесквадратным, если образ каждого бесквадратного слова длины k бесквадратный.

Crochemore^[11] доказывает, что равномерный морфизм час свободна от квадратов тогда и только тогда, когда она свободна от 3 квадратов. Другими словами, час свободна от квадратов тогда и только тогда, когда ${displaystyle h(w)}$ без квадратов для всех без квадратов ш длины 3. Можно найти бесквадратный морфизм с помощью перебор.

алгоритм squarefree_morphism является    выход: бесквадратный морфизм с наименьшим возможным рангом k.    набор ${displaystyle k=3}$    пока Истинный делать        набор k_sf_words к список всех бесквадратных слов длины k над троичным алфавитом для каждого ${displaystyle h(0)}$ в k_sf_words делать            для каждого ${displaystyle h(1)}$ в k_sf_words делать                для каждого ${displaystyle h(2)}$ в k_sf_words делать                    если ${displaystyle h(1)=h(2)}$ тогда                        перемена из текущего цикла (перейти к следующему ${displaystyle h(1)}$)                    если ${displaystyle h(0)eq h(1)}$ и ${displaystyle h(2)eq h(0)}$ тогда                        если ${displaystyle h(w)}$ является свободный от квадратов за все без квадратов ш длины 3 тогда                            возвращаться ${displaystyle h(0),h(1),h(2)}$        приращение k к 1

В тернарном алфавите имеется ровно 144 равномерных бесквадратных морфизма ранга 11 и нет равномерных бесквадратных морфизмов ранга ниже 11.

Чтобы получить бесконечное бесквадратное слово, начните с любого бесквадратного слова, например 0, и последовательно применяем бесквадратный морфизм час к нему. Полученные слова сохраняют свойство квадратичности. Например, пусть час - бесквадратный морфизм, то при ${displaystyle w o infty }$, ${displaystyle h^{w}(0)}$ является бесконечным бесквадратным словом.

Обратите внимание, что если морфизм над тернарным алфавитом не является однородным, то этот морфизм бесквадратный тогда и только тогда, когда он свободен от 5 квадратов.^[11].

Сочетания букв в бесквадратных словах

Расширение слова без квадратов, чтобы избежать ab.

Избегайте двухбуквенных комбинаций

В троичном алфавите бесквадратное слово длиной более 13 содержит все бесквадратные двухбуквенные комбинации.^[12].

Это можно доказать, построив слово без квадратов без двухбуквенной комбинации ab. Как результат, bcbacbcacbaca это самое длинное слово без квадратов без комбинации ab а его длина равна 13.

Обратите внимание, что в алфавите, состоящем из более чем трех букв, есть слова любой длины без квадратов без произвольной комбинации из двух букв.

Избегайте трехбуквенных комбинаций

В троичном алфавите бесквадратное слово длиной более 36 содержит все бесквадратные трехбуквенные комбинации.^[12].

Однако есть слова любой длины без квадратов и без трехбуквенной комбинации. аба.

Обратите внимание, что в алфавите, состоящем из более чем трех букв, есть слова любой длины без квадратов без произвольной комбинации из трех букв.

Плотность письма

Плотность буквы а в конечном слове ш определяется как ${displaystyle {frac {|w|_{a}}{|w|}}}$ куда ${displaystyle |w|_{a}}$ это количество вхождений а в ${displaystyle w}$ и ${displaystyle |w|}$ это длина слова. Плотность буквы а в бесконечном слове ${displaystyle liminf _{l o infty }{frac {|w_{l}|_{a}}{|w_{l}|}}}$ куда ${displaystyle w_{l}}$ это префикс слова ш длины л^[13].

Минимальная плотность письма а в бесконечном тернарном бесквадратном слове равно ${displaystyle {frac {883}{3215}}}$^[13].

Максимальная плотность письма а в бесконечном тернарном бесквадратном слове равно ${displaystyle {frac {255}{653}}}$^[14].

Примечания

1. "A006156 - OEIS". oeis.org. Получено 2019-03-28.
2. Шур, Арсений (2011). «Свойства роста безвластных языков». Обзор компьютерных наук. 6 (5–6): 28–43. Дои:10.1016 / j.cosrev.2012.09.001.
3. Берта, Валери; Риго, Мишель, ред. (2016), «Предисловие», Комбинаторика, слова и символическая динамика, Cambridge University Press, стр. Xi – xviii, Дои:10.1017 / cbo9781139924733.001, ISBN  9781139924733
4. Карпи, Артуро (1988). «Многомерные неповторяющиеся конфигурации». Теоретическая информатика. 56 (2): 233–241. Дои:10.1016/0304-3975(88)90080-1. ISSN  0304-3975.
5. Шур, Арсений (2015). «Эффективное создание слов без квадратов». Теоретическая информатика. 601: 67–72. Дои:10.1016 / j.tcs.2015.07.027.
6. Апостолико, А .; Препарата, Ф. (Февраль 1983 г.). «Оптимальное автономное обнаружение повторов в строке». Теоретическая информатика. 22 (3): 297–315. Дои:10.1016/0304-3975(83)90109-3. ISSN  0304-3975.
7. Крошмор, Макс (октябрь 1981 г.). «Оптимальный алгоритм вычисления повторений в слове». Письма об обработке информации. 12 (5): 244–250. Дои:10.1016/0020-0190(81)90024-7. ISSN  0020-0190.
8. Мэйн, Майкл Джи; Лоренц, Ричард Дж (сентябрь 1984 г.). «Алгоритм O (n log n) для поиска всех повторений в строке». Журнал алгоритмов. 5 (3): 422–432. Дои:10.1016 / 0196-6774 (84) 90021-х. ISSN  0196-6774.
9. Берстель, Жан (1994). Статьи Акселя Туэ о повторах в словах перевод. Départements de mathématiques et d'informatique, Université du Québec à Montréal. ISBN  978-2892761405. OCLC  494791187.
10. Пиявка, Дж. (1957). «Проблема на бусинах». Математика. Вестник. 41: 277–278. Дои:10.1017 / S0025557200236115. Zbl  0079.01101.
11. Берстель, Жан (апрель 1984). "Некоторые недавние результаты о словах, свободных от квадратов". Ежегодный симпозиум по теоретическим аспектам информатики. Конспект лекций по информатике. 166: 14–25. Дои:10.1007/3-540-12920-0_2. ISBN  978-3-540-12920-2.
12. Золотов, Борис (2015). «Другое решение проблемы неповторения слов». arXiv:1505.00019 [math.CO ].
13. Халявин, Андрей (2007). «Минимальная плотность буквы в бесконечном троичном слове без квадратов - 883/3215» (PDF). Журнал целочисленных последовательностей. 10 (2): 3. Bibcode:2007JIntS..10 ... 65K.
14. Очем, Паскаль (2007). «Частота букв в словах без бесконечного повторения». Теоретическая информатика. 380 (3): 388–392. Дои:10.1016 / j.tcs.2007.03.027. ISSN  0304-3975.

Рекомендации

• Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Кристоффель слова и повторы словами. Серия монографий CRM. 27. Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
• Лотэр, М. (1997). Комбинаторика слов. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-59924-5..
• Лотэр, М. (2011). Алгебраическая комбинаторика слов. Энциклопедия математики и ее приложений. 90. С предисловием Жана Берштеля и Доминика Перрена (Перепечатка издания в твердом переплете 2002 г.). Издательство Кембриджского университета. ISBN  978-0-521-18071-9. Zbl  1221.68183.
• Пифей Фогг, Н. (2002). Берте, Валери; Ференци, Себастьен; Mauduit, Christian; Сигель, Энн (ред.). Подстановки в динамике, арифметике и комбинаторике. Конспект лекций по математике. 1794. Берлин: Springer-Verlag. ISBN  978-3-540-44141-0. Zbl  1014.11015.