Слово без квадратов

В комбинаторике , бесквадратным слово это слово (последовательность символов) , который не содержит каких - либо квадратов. Квадрат является слово вида $XX$ , где $X$ не пусто. Таким образом, слово без квадратов также можно определить как слово, избегающее шаблона $XX$ .

Конечные бесквадратные слова [ править ]

Двоичный алфавит [ править ]

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

Тернарный алфавит [ править ]

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

Количество троичных бесквадратных слов длины n ^[1]
$п$	0	1	2	3	4	5	6	7	8	9	10	11	12
${\ Displaystyle с (п)}$	1	3	6	12	18	30	42	60	78	108	144	204	264

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

Алфавит, состоящий из более чем трех букв [ править ]

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

Следующая таблица показывает точную скорость роста $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

Двумерные слова [ править ]

Рассмотрим отображение из в $A$ , где $A$ - алфавит и называется двумерным словом. Позвольте быть входом . Слово - это строка, если существует такое, что и для . ^[3] ${\ displaystyle {\ textbf {w}}}$ ${\ Displaystyle \ mathbb {N} ^ {2}}$ ${\ displaystyle {\ textbf {w}}}$ ${\ displaystyle w_ {m, n}}$ ${\ displaystyle {\ textbf {w}} (м, п)}$ ${\ displaystyle {\ textbf {x}}}$ ${\ displaystyle {\ textbf {w}}}$ $i_{1},i_{2},j_{1},j_{2}$ ${\text{gcd}}(j_{1},j_{2})=1$ $t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}$

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

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

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

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

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

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

N=n\left(1+{\frac {2}{k^{2}}}+{\frac {1}{k^{3}}}+{\frac {4}{k^{4}}}+O\left({\frac {1}{k^{5}}}\right)\right)+O(1).

Обратите внимание, что существует алгоритм, который может проверить квадратность слова длины

n

во времени. Апостолико и Препарата ^[6] дают алгоритм, использующий суффиксные деревья. Крочмор ^[7] использует в своем алгоритме разбиение. Мейн и Лоренц ^[8] предлагают алгоритм, основанный на методе «разделяй и властвуй». Наивная реализация может потребовать времени, чтобы проверить, что слово длины

n не

содержит квадратов .

O(n\log n)

$O(n^{2})$

Бесконечные бесквадратные слова [ править ]

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

Примеры [ править ]

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

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

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...

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

1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...

(последовательность A029883 в OEIS ).

Пиявка «сек морфизма [ править ]

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

0121021201210120210201202120102101201021202102012021 ...

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

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

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

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

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

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

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

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

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

ab

.

Избегайте двухбуквенных комбинаций [ править ]

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

Это можно доказать, построив слово без квадратов без двухбуквенной комбинации $ab$ . В результате $bcba$ $cbca$ $cbaca$ является самым длинным бесквадратным словом без комбинации $ab,$ а его длина равна 13.

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

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

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

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

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

Плотность письма [ править ]

Плотность буква $а$ в конечном слове $ш$ определяются как , где есть число появлений в и является длиной слова. Плотность буквы $a$ в бесконечном слове равна где - префикс слова $w$ длины $l$ . ^[13] ${\frac {|w|_{a}}{|w|}}$ $|w|_{a}$ $w$ $|w|$ $\liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}$ $w_{l}$

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

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

Заметки [ править ]

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

[1] "A006156 - OEIS" . oeis.org . Проверено 28 марта 2019 .

[:1-2] Шур, Арсений (2011). «Свойства роста безвластных языков». Обзор компьютерных наук . 6 (5–6): 28–43. DOI : 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. DOI : 10.1016 / 0304-3975 (88) 90080-1 . ISSN 0304-3975 .

[5] Шур, Арсений (2015). «Эффективное создание слов без квадратов» . Теоретическая информатика . 601 : 67–72. DOI : 10.1016 / j.tcs.2015.07.027 .

[6] Апостолико, А .; Препарата, ФП (февраль 1983 г.). «Оптимальное автономное обнаружение повторов в строке». Теоретическая информатика . 22 (3): 297–315. DOI : 10.1016 / 0304-3975 (83) 90109-3 . ISSN 0304-3975 .

[7] Crochemore, Max (октябрь 1981). «Оптимальный алгоритм вычисления повторов в слове». Письма об обработке информации . 12 (5): 244–250. DOI : 10.1016 / 0020-0190 (81) 90024-7 . ISSN 0020-0190 .

[8] Main, Майкл G; Лоренц, Ричард Дж (сентябрь 1984 г.). «Алгоритм O (n log n) для поиска всех повторений в строке». Журнал алгоритмов . 5 (3): 422–432. DOI : 10.1016 / 0196-6774 (84) 90021-х . ISSN 0196-6774 .

[:4-9] Берстель, Жан (1994). Статьи Акселя Туэ о повторах в словах перевод . Départements de mathématiques et d'informatique, Université du Québec à Montréal. ISBN 978-2892761405. OCLC 494791187 .

[10] Перейти ↑ Leech, J. (1957). «Проблема на бусинах». Математика. Вестник . 41 : 277–278. DOI : 10.1017 / S0025557200236115 . Zbl 0079.01101 .

[:0-11] Берстель, Жан (апрель 1984 г.). «Некоторые недавние результаты по свободным словам» . Ежегодный симпозиум по теоретическим аспектам информатики . Конспект лекций по информатике. 166 : 14–25. DOI : 10.1007 / 3-540-12920-0_2 . ISBN 978-3-540-12920-2.

[:2-12] Золотов, Борис (2015). «Еще одно решение проблемы неповторения слов». arXiv : 1505,00019 [ math.CO ].

[:3-13] Халявин, Андрей (2007). «Минимальная плотность буквы в бесконечном троичном слове без квадратов - 883/3215» (PDF) . Журнал целочисленных последовательностей . 10 (2): 3. Bibcode : 2007JIntS..10 ... 65K .

[14] Очем, Паскаль (2007). «Частота букв в словах без бесконечного повторения». Теоретическая информатика . 380 (3): 388–392. DOI : 10.1016 / j.tcs.2007.03.027 . ISSN 0304-3975 .

[1]