Неизбежный паттерн - Википедия - 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 х in Sigma ^ {*}}$ является экземпляром шаблона ${ displaystyle p in Delta ^ {*}}$ если существует нестираемый полугрупповой морфизм ${ displaystyle f: Delta ^ {*} rightarrow Sigma ^ {*}}$ такой, что ${ Displaystyle f (p) = x}$, куда ${ Displaystyle Sigma ^ {*}}$ обозначает Клини звезда из ${ displaystyle Sigma}$. Не стирание означает, что ${ Displaystyle е (а) 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 х in Sigma ^ {*}}$ должен соответствовать ${ displaystyle p}$; формально: если ${ Displaystyle существует п in mathrm {N}. forall x in Sigma ^ {*}. (| x | geq n подразумевает x { text {соответствует}} 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 ш в 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 существует 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 п in mathrm {N}}$ представляют количество различных символов узора ${ displaystyle p}$. Если ${ displaystyle | p | geq 2 ^ {n}}$, тогда ${ displaystyle p}$ можно избежать.^[3]

Слова Зимина

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

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

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

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

Учитывая конечный алфавит ${ displaystyle Sigma}$, позволять ${ Displaystyle f (п, | Sigma |)}$ представляют собой самые маленькие ${ Displaystyle м ин mathrm {Z} ^ {+}}$ такой, что ${ displaystyle w}$ совпадения ${ displaystyle Z_ {n}}$ для всех ${ Displaystyle ш в 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 х 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 существует 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 пи _ {р} ^ {'} (п)}$ определены для окраски краев.

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

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

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

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

Существует абсолютная постоянная ${ displaystyle c}$, так что ${ displaystyle pi _ {p} (n) leq cn ^ { frac {m (p)} {m (p) -1}} leq cn ^ {2}}$ для всех моделей ${ displaystyle p}$ с ${ Displaystyle м (р) 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 к geq 1}$, куда ${ displaystyle K_ {n}}$ это полный график из ${ displaystyle n}$ вершины.^[8]

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

Учитывая шаблон ${ displaystyle p}$ такой, что ${ Displaystyle м (р) geq 2}$, а дерево ${ displaystyle T}$ со степенью ${ Displaystyle п 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 х ^ {п}}$ за ${ Displaystyle п 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 (п)}$ точная нижняя грань показателей ${ displaystyle k}$ такой, что ${ displaystyle x ^ {k}}$ можно избежать на алфавите размера ${ displaystyle n}$. Также см Теорема Дежана.

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

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

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

• Аллуш, Жан-Поль; Шаллит, Джеффри (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.