Неизбежный образец - Unavoidable pattern

В математика и теоретическая информатика, узор - это неизбежный образец если это неизбежно в любом конечном алфавите.

Определения

Шаблон

Как слово, узор (также называемый срок) - последовательность символов над некоторыми алфавит.

Минимальная кратность узора ${\displaystyle p}$ является ${\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)}$ куда ${\displaystyle \mathrm {count_{p}} (x)}$ это количество вхождений символа ${\displaystyle x}$ в образце ${\displaystyle p}$. Другими словами, это количество вхождений в ${\displaystyle p}$ наименее часто встречающегося символа в ${\displaystyle p}$.

Пример

Учитывая конечные алфавиты ${\displaystyle \Sigma }$ и ${\displaystyle \Delta }$, слово ${\displaystyle x\in \Sigma ^{*}}$ является экземпляром шаблона ${\displaystyle p\in \Delta ^{*}}$ если существует нестираемый полугрупповой морфизм ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$ такой, что ${\displaystyle f(p)=x}$, куда ${\displaystyle \Sigma ^{*}}$ обозначает Клини звезда из ${\displaystyle \Sigma }$. Не стирание означает, что ${\displaystyle f(a)\neq \varepsilon }$ для всех ${\displaystyle a\in \Delta }$, куда ${\displaystyle \varepsilon }$ обозначает пустой строкой.

Избегание / соответствие

Слово ${\displaystyle w}$ говорят матч, или же сталкиваться, шаблон ${\displaystyle p}$ если фактор (также называемый подслово или же подстрока ) из ${\displaystyle w}$ это пример ${\displaystyle p}$. Иначе, ${\displaystyle w}$ говорят, чтобы избежать ${\displaystyle p}$, или быть ${\displaystyle p}$-свободный. Это определение можно обобщить на случай бесконечного ${\displaystyle w}$, основанный на обобщенном определении «подстроки».

Избегаемость / неизбежность по определенному алфавиту

Шаблон ${\displaystyle p}$ является неизбежный на конечном алфавите ${\displaystyle \Sigma }$ если каждое достаточно длинное слово ${\displaystyle x\in \Sigma ^{*}}$ должен соответствовать ${\displaystyle p}$; формально: если ${\displaystyle \exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies x{\text{ matches }}p)}$. Иначе, ${\displaystyle p}$ является можно избежать на ${\displaystyle \Sigma }$, что означает, что существует бесконечно много слов в алфавите ${\displaystyle \Sigma }$ что избежать ${\displaystyle p}$.

К Лемма Кёнига, шаблон ${\displaystyle p}$ можно избежать на ${\displaystyle \Sigma }$ если и только если существует бесконечное слово ${\displaystyle w\in \Sigma ^{\omega }}$ это позволяет избежать ${\displaystyle p}$.^[1]

Максимальный ${\displaystyle p}$-свободное слово

Учитывая шаблон ${\displaystyle p}$ и алфавит ${\displaystyle \Sigma }$. А ${\displaystyle p}$-свободное слово ${\displaystyle w\in \Sigma ^{*}}$ это максимальный ${\displaystyle p}$-бесплатное слово ${\displaystyle \Sigma }$ если ${\displaystyle aw}$ и ${\displaystyle wa}$ матч ${\displaystyle p}$ ${\displaystyle \forall a\in \Sigma }$.

Избегаемый / неизбежный образец

Шаблон ${\displaystyle p}$ это неизбежный паттерн (также называемый срок блокировки) если ${\displaystyle p}$ неизбежно в любом конечном алфавите.

Если шаблон неизбежен и не ограничен конкретным алфавитом, то по умолчанию он неизбежен для любого конечного алфавита. И наоборот, если говорят, что шаблон можно избежать и не ограничен определенным алфавитом, то по умолчанию его можно избежать для некоторого конечного алфавита.

${\displaystyle k}$-авторизованный / ${\displaystyle k}$- неизбежный

Шаблон ${\displaystyle p}$ является ${\displaystyle k}$- избежать, если ${\displaystyle p}$ можно избежать на алфавите ${\displaystyle \Sigma }$ размера ${\displaystyle k}$. Иначе, ${\displaystyle p}$ является ${\displaystyle k}$- неизбежно, что означает ${\displaystyle p}$ неизбежно для любого алфавита размера ${\displaystyle k}$.^[2]

Если шаблон ${\displaystyle p}$ является ${\displaystyle k}$-Избежать тогда ${\displaystyle p}$ является ${\displaystyle g}$- избежать всех ${\displaystyle g\geq k}$.

Учитывая конечный набор шаблонов, которых можно избежать ${\displaystyle S=\{p_{1},p_{2},...,p_{i}\}}$, существует бесконечное слово ${\displaystyle w\in \Sigma ^{\omega }}$ такой, что ${\displaystyle w}$ избегает всех моделей ${\displaystyle S}$.^[1] Позволять ${\displaystyle \mu (S)}$ обозначим размер минимального алфавита ${\displaystyle \Sigma ^{'}}$такой, что ${\displaystyle \exists w^{'}\in {\Sigma ^{'}}^{\omega }}$ избегая всех моделей ${\displaystyle S}$.

Индекс избегаемости

Индекс избегаемости паттерна ${\displaystyle p}$ самый маленький ${\displaystyle k}$ такой, что ${\displaystyle p}$ является ${\displaystyle k}$-избежать, и ${\displaystyle \infty }$ если ${\displaystyle p}$ неизбежно.^[1]

Характеристики

• Шаблон ${\displaystyle q}$можно избежать, если ${\displaystyle q}$пример паттерна, которого можно избежать ${\displaystyle p}$.^[3]
• Позвольте избежать шаблонов ${\displaystyle p}$ быть фактором шаблона ${\displaystyle q}$, тогда ${\displaystyle q}$ также можно избежать.^[3]
• Шаблон ${\displaystyle q}$ неизбежно тогда и только тогда, когда ${\displaystyle q}$ фактор некоторой неизбежной закономерности ${\displaystyle p}$.
• Учитывая неизбежный образец ${\displaystyle p}$ и символ ${\displaystyle a}$ не в ${\displaystyle p}$, тогда ${\displaystyle pap}$ неизбежно.^[3]
• Учитывая неизбежный образец ${\displaystyle p}$, то разворот ${\displaystyle p^{R}}$ неизбежно.
• Учитывая неизбежный образец ${\displaystyle p}$, существует символ ${\displaystyle a}$ такой, что ${\displaystyle a}$ происходит ровно один раз в ${\displaystyle p}$.^[3]
• Позволять ${\displaystyle n\in \mathrm {N} }$ представляют количество различных символов узора ${\displaystyle p}$. Если ${\displaystyle |p|\geq 2^{n}}$, тогда ${\displaystyle p}$ можно избежать.^[3]

Слова Зимина

Основная статья: Sesquipower

Данный алфавит ${\displaystyle \Delta =\{x_{1},x_{2},...\}}$, Зиминские слова (шаблоны) определяются рекурсивно ${\displaystyle Z_{n+1}=Z_{n}x_{n+1}Z_{n}}$ за ${\displaystyle n\in \mathrm {Z} ^{+}}$ и ${\displaystyle Z_{1}=x_{1}}$.

Неизбежность

Все слова Зимина неизбежны.^[4]

Слово ${\displaystyle w}$ неизбежно тогда и только тогда, когда оно является множителем слова Зимина.^[4]

Учитывая конечный алфавит ${\displaystyle \Sigma }$, позволять ${\displaystyle f(n,|\Sigma |)}$ представляют собой самые маленькие ${\displaystyle m\in \mathrm {Z} ^{+}}$ такой, что ${\displaystyle w}$ совпадения ${\displaystyle Z_{n}}$ для всех ${\displaystyle w\in \Sigma ^{m}}$. У нас есть следующие свойства:^[5]

• ${\displaystyle f(1,q)=1}$
• ${\displaystyle f(2,q)=2q+1}$
• ${\displaystyle f(3,2)=29}$
• ${\displaystyle f(n,q)\leq {^{n-1}q}=\underbrace {q^{q^{\cdot ^{\cdot ^{q}}}}} _{n-1}}$

${\displaystyle Z_{n}}$ - самый длинный неизбежный узор, построенный по алфавиту ${\displaystyle \Delta =\{x_{1},x_{2},...,x_{n}\}}$ поскольку ${\displaystyle |Z_{n}|=2^{n}-1}$.

Уменьшение рисунка

Бесплатное письмо

Учитывая шаблон ${\displaystyle p}$ над некоторым алфавитом ${\displaystyle \Delta }$, мы говорим ${\displaystyle x\in \Delta }$ бесплатно для ${\displaystyle p}$ если существуют подмножества ${\displaystyle A,B}$ из ${\displaystyle \Delta }$ такие, что выполняется следующее:

1. ${\displaystyle uv}$ фактор ${\displaystyle p}$ и ${\displaystyle u\in A}$ ↔ ${\displaystyle uv}$ фактор ${\displaystyle p}$ и ${\displaystyle v\in B}$
2. ${\displaystyle x\in A\backslash B\cup B\backslash A}$

Например, пусть ${\displaystyle p=abcbab}$, тогда ${\displaystyle b}$ бесплатно для ${\displaystyle p}$ поскольку существует ${\displaystyle A=ac,B=b}$ удовлетворяющие указанным выше условиям.

Уменьшать

Шаблон ${\displaystyle p\in \Delta ^{*}}$ уменьшает узор ${\displaystyle q}$ если существует символ ${\displaystyle x\in \Delta }$ такой, что ${\displaystyle x}$ бесплатно для ${\displaystyle p}$, и ${\displaystyle q}$ можно получить, удалив все вхождения ${\displaystyle x}$ из ${\displaystyle p}$. Обозначим это отношение через ${\displaystyle p{\stackrel {x}{\rightarrow }}q}$.

Например, пусть ${\displaystyle p=abcbab}$, тогда ${\displaystyle p}$ может уменьшиться до ${\displaystyle q=aca}$ поскольку ${\displaystyle b}$ бесплатно для ${\displaystyle p}$.

Заблокировано

Слово ${\displaystyle w}$ считается заблокированным, если ${\displaystyle w}$ не имеет бесплатного письма; следовательно ${\displaystyle w}$ не может быть уменьшено.^[6]

Транзитивность

Данные шаблоны ${\displaystyle p,q,r}$, если ${\displaystyle p}$ сводится к ${\displaystyle q}$ и ${\displaystyle q}$ сводится к ${\displaystyle r}$, тогда ${\displaystyle p}$ сводится к ${\displaystyle r}$. Обозначим это отношение через ${\displaystyle p{\stackrel {*}{\rightarrow }}r}$.

Неизбежность

Шаблон ${\displaystyle p}$ неизбежно тогда и только тогда, когда ${\displaystyle p}$ сокращается до слова длиной один; следовательно ${\displaystyle \exists w}$ такой, что ${\displaystyle |w|=1}$ и ${\displaystyle p{\stackrel {*}{\rightarrow }}w}$.^[7][4]

Избегание графических шаблонов^[8]

Избегание / соответствие на конкретном графике

Учитывая простой график ${\displaystyle G=(V,E)}$, край раскраска ${\displaystyle c:E\rightarrow \Delta }$ соответствует шаблону ${\displaystyle p}$ если существует простой дорожка ${\displaystyle P=[e_{1},e_{2},...,e_{r}]}$ в ${\displaystyle G}$ такая, что последовательность ${\displaystyle c(P)=[c(e_{1}),c(e_{2}),...,c(e_{r})]}$ совпадения ${\displaystyle p}$. Иначе, ${\displaystyle c}$ говорят, чтобы избежать ${\displaystyle p}$ или быть ${\displaystyle p}$-свободный.

Аналогично раскраска вершины ${\displaystyle c:V\rightarrow \Delta }$ соответствует шаблону ${\displaystyle p}$ если существует простой дорожка ${\displaystyle P=[c_{1},c_{2},...,c_{r}]}$ в ${\displaystyle G}$ такая, что последовательность ${\displaystyle c(P)}$ совпадения ${\displaystyle p}$.

Хроматическое число образца

Хроматическое число образца ${\displaystyle \pi _{p}(G)}$ минимальное количество различных цветов, необходимое для ${\displaystyle p}$-свободная раскраска вершин ${\displaystyle c}$ по графику ${\displaystyle G}$.

Позволять ${\displaystyle \pi _{p}(n)=\max\{\pi _{p}(G):G\in G_{n}\}}$ куда ${\displaystyle G_{n}}$ - множество всех простых графов с максимумом степень не более чем ${\displaystyle n}$.

По аналогии, ${\displaystyle \pi _{p}^{'}(G)}$ и ${\displaystyle \pi _{p}^{'}(n)}$ определены для окраски краев.

Избегаемость / Неизбежность на графах

Шаблон ${\displaystyle p}$ можно избежать на графах, если ${\displaystyle \pi _{p}(n)}$ ограничен ${\displaystyle c_{p}}$, куда ${\displaystyle c_{p}}$ только зависит от ${\displaystyle p}$.

• Избегание слов можно выразить как конкретный случай избегания на графиках; отсюда шаблон ${\displaystyle p}$ можно избежать в любом конечном алфавите тогда и только тогда, когда ${\displaystyle \pi _{p}(P_{n})\leq c_{p}}$ для всех ${\displaystyle n\in \mathrm {Z} ^{+}}$, куда ${\displaystyle P_{n}}$ это график ${\displaystyle n}$ вершины соединены.

Вероятностная оценка ${\displaystyle \pi _{p}(n)}$

Существует абсолютная постоянная ${\displaystyle c}$, так что ${\displaystyle \pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}}$ для всех моделей ${\displaystyle p}$ с ${\displaystyle m(p)\geq 2}$.^[8]

Учитывая шаблон ${\displaystyle p}$, позволять ${\displaystyle n}$ представляют собой количество различных символов ${\displaystyle p}$. Если ${\displaystyle |p|\geq 2^{n}}$, тогда ${\displaystyle p}$ можно избежать на графиках.

Явные раскраски

Учитывая шаблон ${\displaystyle p}$ такой, что ${\displaystyle count_{p}(x)}$ даже для всех ${\displaystyle x\in p}$, тогда ${\displaystyle \pi _{p}^{'}(K_{2}^{k})\leq 2^{k}-1}$ для всех ${\displaystyle k\geq 1}$, куда ${\displaystyle K_{n}}$ это полный график из ${\displaystyle n}$ вершины.^[8]

Учитывая шаблон ${\displaystyle p}$ такой, что ${\displaystyle m(p)\geq 2}$, а произвольный дерево ${\displaystyle T}$, позволять ${\displaystyle S}$ быть набором всех подшаблонов, которых можно избежать, и их отражений ${\displaystyle p}$. потом ${\displaystyle \pi _{p}(T)\leq 3\mu (S)}$.^[8]

Учитывая шаблон ${\displaystyle p}$ такой, что ${\displaystyle m(p)\geq 2}$, а дерево ${\displaystyle T}$ со степенью ${\displaystyle n\geq 2}$. Позволять ${\displaystyle S}$ быть набором всех подшаблонов, которых можно избежать, и их отражений ${\displaystyle p}$, тогда ${\displaystyle \pi _{p}^{'}(T)\leq 2(n-1)\mu (S)}$.^[8]

Примеры

• В Последовательность Туэ – Морса не имеет кубов и перекрытий; следовательно, он избегает шаблонов ${\displaystyle xxx}$ и ${\displaystyle xyxyx}$.^[2]
• А слово без квадратов один избегает шаблона ${\displaystyle xx}$. Слово над алфавитом ${\displaystyle \{0,\pm 1\}}$ полученный путем взятия первая разница последовательности Туэ – Морса является примером бесконечного слова без квадратов.^[9][10]
• Шаблоны ${\displaystyle x}$ и ${\displaystyle xyx}$ неизбежны в любом алфавите, поскольку они являются множителями слов Зимина.^[11][1]
• Модели власти ${\displaystyle x^{n}}$ за ${\displaystyle n\geq 3}$ 2-избежать.^[1]
• Все бинарные паттерны можно разделить на три категории:^[1]
  • ${\displaystyle \varepsilon ,x,xyx}$ неизбежны.
  • ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$ имеют индекс избегаемости 3.
  • другие имеют индекс избегаемости 2.
• ${\displaystyle abwbaxbcyaczca}$ имеет индекс избегаемости 4, как и другие закрытые слова.^[6]
• ${\displaystyle abvacwbaxbcycdazdcd}$ имеет индекс избегаемости 5.^[12]
• Повторяющийся порог ${\displaystyle RT(n)}$ точная нижняя грань показателей ${\displaystyle k}$ такой, что ${\displaystyle x^{k}}$ можно избежать на алфавите размера ${\displaystyle n}$. Также см Теорема Дежана.

Открытые проблемы

• Есть ли закономерность, которой можно избежать ${\displaystyle p}$ такой, что индекс избегаемости ${\displaystyle p}$ 6?
• Учитывая произвольную схему ${\displaystyle p}$, существует ли алгоритм определения индекса избегаемости ${\displaystyle p}$?^[1]
• Можно ли также избежать всех шаблонов, которых можно избежать, на графиках?^[13]

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

1. Лотэр, М. (2002). Алгебраическая комбинаторика слов. Издательство Кембриджского университета.
2. Комбинаторика слов: слова Кристоффеля и повторения слов. American Mathematical Soc. п. 127. ISBN  978-0-8218-7325-0.
3. Шмидт, Урсула (1987-08-01). «Долгие неизбежные закономерности». Acta Informatica. 24 (4): 433–445. Дои:10.1007 / BF00292112. ISSN  1432-0525. S2CID  7928450.
4. Зимин, А.И. (1984). «Блокирующие наборы условий». Математика СССР-Сборник. 47 (2): 353–364. Дои:10.1070 / SM1984v047n02ABEH002647. ISSN  0025-5734.
5. Джошуа, Купер; Рорабо, Дэнни (2013). Границы уклонения от слов Зимина. arXiv:1409.3080. Bibcode:2014arXiv1409.3080C.
6. Бейкер, Кирби А .; Макналти, Джордж Ф .; Тейлор, Уолтер (1989-12-18). «Проблемы роста для слов, которых можно избежать». Теоретическая информатика. 69 (3): 319–345. Дои:10.1016/0304-3975(89)90071-6. ISSN  0304-3975.
7. Бин, Дуайт Р .; Эренфойхт, Анджей; Макналти, Джордж Ф. (1979). «Избегать шаблонов в цепочках символов». Тихоокеанский математический журнал. 85 (2): 261–294. Дои:10.2140 / pjm.1979.85.261. ISSN  0030-8730.
8. Грычук, Ярослав (28 мая 2007 г.). «Избежание закономерностей на графиках». Дискретная математика. Четвертая Караковская конференция по теории графов. 307 (11): 1341–1346. Дои:10.1016 / j.disc.2005.11.071. ISSN  0012-365X.
9. Комбинаторика слов: слова Кристоффеля и повторения слов. American Mathematical Soc. п. 97. ISBN  978-0-8218-7325-0.
10. Фогг, Н. Питеас (23 сентября 2002 г.). Подстановки в динамике, арифметике и комбинаторике. Springer Science & Business Media. п. 104. ISBN  978-3-540-44141-0.
11. Аллуш, Жан-Поль; Шаллит, Джеффри; Шаллит, профессор Джеффри (21 июля 2003 г.). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. п. 24. ISBN  978-0-521-82332-6.
12. Кларк, Рональд Дж. (01.04.2006). «Существование модели, которой можно избежать пяти, но четыре неизбежны». Международный журнал алгебры и вычислений. 16 (2): 351–367. Дои:10.1142 / S0218196706002950. ISSN  0218-1967.
13. Грычук, Ярослав (28 мая 2007 г.). «Избежание закономерностей на графиках». Дискретная математика. Четвертая Караковская конференция по теории графов. 307 (11): 1341–1346. Дои:10.1016 / j.disc.2005.11.071. ISSN  0012-365X.

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