close

Вход

Забыли?

вход по аккаунту

?

Комбинаторные свойства факторных языков перестановок

код для вставкиСкачать
На правах рукописи
Валюженич Александр Андреевич
КОМБИНАТОРНЫЕ СВОЙСТВА ФАКТОРНЫХ ЯЗЫКОВ
ПЕРЕСТАНОВОК
01.01.09 — дискретная математика
и математическая кибернетика
Автореферат
диссертации на соискание ученой степени
кандидата физико-математических наук
Новосибирск-2015
Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Новосибирском национальном
исследовательском государственном университете».
Научный руководитель:
доктор физико-математических наук
Кротов Денис Станиславович.
Официальные оппоненты:
Шалагинов Леонид Викторович
кандидат физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Челябинский государственный университет», доцент кафедры компьютерной безопасности и прикладной
алгебры;
Шур Арсений Михайлович
доктор физико-математических наук, профессор, Федеральное государственное автономное образовательное учреждение высшего
профессионального образования «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина», профессор
кафедры алгебры и дискретной математики.
Ведущая организация: Федеральное государственное бюджетное
образовательное учреждение высшего образования «Московский
государственный университет имени М. В. Ломоносова».
Защита состоится 20 мая 2015 года в 17 часов 30 минут на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск,
пр. Академика Коптюга 4.
С диссертацией можно ознакомиться в библиотеке и на сайте Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук,
http://math.nsc.ru.
Автореферат разослан «15» апреля 2015 г.
Ученый секретарь диссертационного совета
доктор физико-математических наук
Ю. В. Шамардин
Общая характеристика работы
Актуальность и степень разработанности темы исследования. В данной работе исследуются свойства факторных языков перестановок: мы изучаем языки подперестановок бесконечных перестановок; а также языки конечных перестановок, избегающих подпоследовательностей с определенными свойствами. Эти задачи относятся к комбинаторике слов, бесконечных перестановок, а также теории паттернов
в перестановках. Основы комбинаторики слов и теории паттернов в перестановках изложены в монографиях [4, 11] и [13, 36] соответственно;
недавний обзор по бесконечным перестановкам может быть найден в
работе [31].
Приведем основные определения. Алфавитом называется конечное
(непустое) множество элементов, которые будем называть символами или буквами. Далее алфавит будем обозначать через Σ. Конечным словом длины n над алфавитом Σ называется последовательность
u = u1 . . . un из n символов алфавита Σ. Длину конечного слова u, то
есть число символов в нем, обозначим через |u|. Слово длины 0 называется пустым и обозначается через ε. Множество всех конечных слов
над алфавитом Σ обозначается через Σ∗ .
Бесконечным словом над алфавитом Σ называется бесконечная
вправо последовательность ω = ω1 ω2 ω3 . . . символов алфавита Σ. Конкатенацией конечного слова u и слова v (конечного или бесконечного) называется слово x = x1 x2 . . . такое, что xi = ui для i ≤ |u| и
xi = vi−|u| для i > |u|. Конкатенация слов u и v обозначается через
uv. Слово v называется подсловом конечного или бесконечного слова u, если существуют слова s1 и s2 такие, что u = s1 vs2 . Если при
этом s1 = ε (s2 = ε), то v называется префиксом (суффиксом) слова
u. Вхождением слова u ∈ Σ∗ в слово ω называется пара (u, m) такая,
что u = ωm+1 ωm+2 . . . ωm+n . Комбинаторной сложностью cω (n) бесконечного слова ω называется число его различных подслов длины n.
Бесконечное слово вида ω = vvv . . . обозначается через v ω . Бесконечное
слово ω называется периодическим, если ω = uv ω для некоторых конечных слов u и v. Бесконечное слово ω называется непериодическим, если
его нельзя представить в виде ω = uv ω для некоторых конечных слов
u и v. Языком называется произвольное подмножество Σ∗ . Язык называется факторным, если он с каждым своим элементом содержит все
его подслова, то есть замкнут относительно операции взятия подслова.
3
Нетрудно видеть, что язык подслов F (ω) произвольного бесконечного
слова ω является факторным.
Отображение h : Σ∗ −→ Σ∗ называется морфизмом, если h(xy) =
h(x)h(y) для любых слов x, y ∈ Σ∗ . Нетрудно видеть, что морфизм однозначно определяется образами всех символов алфавита Σ, которые
будем называть блоками. Морфизм называется l–равноблочным, если
все его блоки имеют длину l. Морфизм ϕ : Σ∗ −→ Σ∗ называется маркированным, если его блоки имеют вид ϕ(a) = ba xa ca , где xa — некоторое
произвольное слово, ba и ca — символы алфавита Σ, и все ba (как и все
ca ) различны для разных символов алфавита. Морфизм ϕ : Σ∗ −→ Σ∗ ,
где Σ = {0, 1}, будем называть бинарным. Морфизм ϕ : Σ∗ −→ Σ∗ называется нестирающим, если все его блоки непусты. Произвольное слово
ω называется неподвижной точкой морфизма ϕ, если ω = ϕ(ω).
Будем говорить, что l–равноблочный маркированный бинарный
морфизм ϕ такой, что слово ϕ(0) начинается с 0, принадлежит классу Ql , если ϕ имеет следующие свойства (мы предполагаем, что l ≥ 2):
Свойства.
1. Если ϕ(0) = 0u0x для некоторого слова x, то 0u1 не является
подсловом ϕ(0) и ϕ(1), и 0u не является суффиксом ϕ(0) и ϕ(1).
2. Если ϕ(1) = 1u1x для некоторого слова x, то 1u0 не является
подсловом ϕ(0) и ϕ(1), и 1u не является суффиксом ϕ(0) и ϕ(1).
Бинарный морфизм ϕ будем называть сравнимым, если ϕ ∈ Ql для
некоторого l ≥ 2. Морфизм вида ϕ(0) = 01k , ϕ(1) = 0, где k ≥ 2, будем
далее называть обобщенным морфизмом Фибоначчи.
Конечной перестановкой x длины n будем называть упорядоченную
тройку x = h{1, . . . , n}, <x , <i, где <x — это некоторый линейный порядок на множестве {1, 2, . . . , n}, а < — естественный порядок на множестве {1, 2, . . . , n}. В дальнейшем будем писать x = x1 x2 . . . xn , если {x1 , x2 , . . . , xn } — это некоторая перестановка чисел из множества
{1, 2, . . . , n} такая, что xi < xj , если и только если i <x j. Рассмотрим произвольную перестановку π = π1 π2 . . . πn длины n. Классическим паттерном (или просто паттерном) называется перестановка x
длины k. Подпоследовательность πi1 πi2 . . . πik называется вхождением
классического паттерна x = x1 x2 . . . xk в перестановку π, если πis < πit
тогда и только тогда, когда xs < xt для всех 1 ≤ s < t ≤ k. Будем говорить, что перестановка π избегает паттерн x, если она не содержит
4
вхождений этого паттерна. Множество перестановок длины n, избегающих паттерна x, обозначим через Sn (x); мощность множества Sn (x)
обозначим через sn (x).
Бесконечной перестановкой будем называть упорядоченную тройку
δ = hN, <δ , <i, где <δ — это некоторый линейный порядок на множестве натуральных чисел N, а < — естественный порядок на множестве
натуральных чисел. Пусть δ — бесконечная перестановка. Конечную
перестановку x длины n такую, что i <x j тогда и только тогда, когда
m + i − 1 <δ m + j − 1 обозначим через δ[m, m + n − 1]. Конечная перестановка π длины n называется подперестановкой длины n бесконечной
перестановки δ, если π = δ[i, i + n − 1] для некоторого i > 0. Комбинаторной сложностью λδ (n) бесконечной перестановки δ называется
число ее различных подперестановок длины n.
Пусть ω — произвольное бесконечное непериодическое слово над алфавитом Σ = {0, 1, . . . , q − 1}. Непериодическому
P слову ω сопоставим
действительное число Rω (i) = 0, ωi ωi+1 . . . = k≥0 ωi+k q −(k+1) . Определим бесконечную перестановку δω , порождаемую словом ω, как упорядоченную тройку δω = hN, <δω , <i, где <δω и < — линейные порядки
на множестве натуральных чисел N. При этом <δω определяется следующим образом: i<δω j тогда и только тогда, когда Rω (i) < Rω (j). Отметим, что порядок <δω совпадает с лексикографическим порядком на
множестве суффиксов ω[i] слова ω (ω[i] = ωi ωi+1 . . .). Пусть u — некоторое подслово бесконечного непериодического слова ω. Вхождение (u, m)
слова u длины n порождает перестановку π, если π = δω [m + 1, m + n].
Подслово u слова ω порождает перестановку π, если существует вхождение (u, m), которое порождает π. Множество всех перестановок, порожденных словом u, обозначим через Hu . Языком перестановок будем
называть произвольное множество конечных перестановок. Язык перестановок будем называть факторным, если он с каждым своим элементом содержит все его подперестановки, то есть замкнут относительно
операции взятия подперестановки.
Для произвольных функций f, g : N → N будем писать f = Θ(g)
(f = O(g)), если существуют такие константы C1 , C2 > 0 (C > 0), что
C1 ·g(n) ≤ f (n) ≤ C2 · g(n) (f (n) ≤ C · g(n)) для любого n ∈ N. Функцию
f : N → N будем называть кусочно–линейной, если f = Θ(n).
В главах 2, 3 и 4 мы впервую очередь концентрируемся на изучении функции комбинаторной сложности бесконечных перестановок.
Так как комбинаторная сложность бесконечных перестановок является
5
естественным аналогом комбинаторной сложности бесконечных слов,
то приведем небольшой обзор по работам о комбинаторной сложности
бесконечных слов. Кроме того, приведем обзор работ по бесконечным
перестановкам.
Комбинаторная сложность бесконечного слова — функция неубывающая. Также для нее выполнены тривиальные оценки 1 ≤ cω (n) ≤ q n ,
где q — мощность алфавита Σ. При этом, далеко не любая неубывающая функция f : N → N, для которой 1 ≤ f (n) ≤ q n , является функцией
комбинаторной сложности для некоторого бесконечного слова над алфавитом мощности q. Обзор известных условий, которым удовлетворяет функция комбинаторной сложности бесконечного слова может быть
найден в работе [30]. Полная характеризация функций, являющихся
функцией комбинаторной сложности для некоторого бесконечного слова, до сих пор неизвестна.
Заметим, что если ω — бесконечное периодическое слово, то его комбинаторная сложность, начиная с некоторого момента, становится константой, то есть существует N такое, что cω (n) = c0 для некоторой константы c0 при n ≥ N . Классический результат Морса и Хэдлунда 1940
года [49] утверждает, что если ω — непериодическое слово, то его комбинаторная сложность — функция строго возрастающая и cω (n) ≥ n + 1.
Бесконечное слово ω, для которого cω (n) = n + 1, называется словом
Штурма. Таким образом, слова Штурма имеют наименьшую возможную комбинаторную сложность среди непериодических слов. Класс слов
Штурма хорошо изучен, в частности существует много эквивалентных
определений слов Штурма (см. обзор [11], а также главу 2 монографии [43]). Классическим примером слова Штурма является слово Фибоначчи ω — неподвижная точка морфизма ϕ(0) = 01, ϕ(1) = 0.
Кроме того, специалистами активно изучаются бесконечные слова с
кусочно-линейной комбинаторной сложностью [20, 25, 26, 42]. Одним из
самых сильных и нетривиальных результатов в данной области является результат Ж. Кассеня [20], утверждающий, что для любого слова ω с кусочно-линейной комбинаторной сложностью первые разности
его комбинаторной сложности cω (n + 1) − cω (n) ограничены некоторой
константой. Из последних результатов стоит отметить работу Ж. Леруа [42]. При этом, достаточно удобная характеризация слов с кусочнолинейной комбинаторной сложностью до сих пор не найдена.
Одной из первых работ о комбинаторной сложности неподвижных
точек морфизмов является статья А. Эренфойхта, К. П. Ли и Г. Розен6
берга [28] 1975 года. В этой работе они доказали, что для неподвижной
точки морфизма ω верно соотношение cω (n) = O(n2 ), то есть, что рост
комбинаторной сложности не более чем квадратичный.
В 1984 году Ж.–Ж. Пансьо [50] доказал, что если ω — неподвижная точка морфизма, то выполнено одно из следующих условий:
cω (n) = Θ(1), либо cω (n) = Θ(n), либо cω (n) = Θ(n log log n), либо
cω (n) = Θ(n log n), либо cω (n) = Θ(n2 ). Кроме того, в той же работе
приведен алгоритм, позволяющий по морфизму определить, к какому
из пяти классов принадлежит комбинаторная сложность его неподвижной точки.
Точная формула комбинаторной сложности слова Туэ-Морса (неподвижной точки морфизма ϕ(0) = 01, ϕ(1) = 10) была впервые получена
в 1989 году С. Брлеком в [16] и независимо А. де Лукой и С. Варриччио
в [41]. Позднее этот результат был переоткрыт в работе С. В. Августиновича [1].
В работе [19] Ж. Кассень разработал алгоритм, позволяющий вычислить комбинаторную сложность неподвижных точек бипрефиксных
морфизмов. Стоит отметить, что в этой работе впервые был применен
ставший уже классическим, метод биспециальных слов. Позднее в [6] С.
В. Августинович и А. Э. Фрид переоткрыли метод биспециальных слов
и получили точную формулу для комбинаторной сложности неподвижных точек бипрефиксных морфизмов. Точная формула для комбинаторной сложности неподвижных точек равноблочных буферных морфизмов была найдена А. Э. Фрид в работе [33]. Из последних результатов в данной области отметим результат К. Клоуды [39], который описал множество всех биспециальных слов для неподвижных точек циркулярных non-pushy морфизмов (зная множество биспециальных слов
бесконечного слова, легко найти его комбинаторную сложность).
Теперь приведем краткий обзор результатов о бесконечных перестановках. Бесконечные перестановки как линейные порядки на множестве
натуральных чисел впервые были введены в работе А. Э. Фрид и Д. Г.
Фон-дер-Флаасса [34], хотя некоторые проблемы, связанные с ними, исследовались и ранее. К примеру, в статье [24] 1977 года рассматривались
перестановки, избегающие длинных монотонных арифметических паттернов. Напомним, что конечное или бесконечное слово ω = ω1 ω2 . . . называется t–периодическим, если ωi = ωi+t для всех i таких, что символ
ωi+t корректно определен. В работе [34] А. Э. Фрид и Д. Г. Фон-дерФлаасс рассмотрели один из возможных аналогов t–периодичности для
7
перестановок: конечная или бесконечная перестановка x называется t–
периодической, если i <x j тогда и только тогда, когда i + t <x j + t для
всех допустимых i и j.
В комбинаторике слов хорошо известна следующая теорема Файна–
Вильфа 1965 года:
• Если конечное слово длины не менее p + q − (p, q) является p–периодическим и q–периодическим, то оно является (p, q)–
периодическим. Кроме того, существует слово длины p+q−(p, q)−
1, которое p–периодическое и q–периодическое, но при этом не является (p, q)–периодическим.
В работе А. Э. Фрид [32] был получен аналог этой теоремы для перестановок. Как мы уже отмечали выше, бесконечное слово является периодическим тогда и только тогда, когда его комбинаторная сложность,
начиная с некоторого момента, становится константой; кроме того, для
любого непериодического слова ω выполнено неравенство cω (n) ≥ n + 1.
Аналогичные вопросы, связанные с комбинаторной сложностью периодических и непериодических бесконечных перестановок, впервые были
исследованы в работе А. Э. Фрид и Д. Г. Фон-дер-Флаасса [34].
Понятие бесконечной перестановки, порожденной бесконечным словом, впервые было введено в работе М. А. Макарова [45]. В той же
работе была получена формула для числа перестановок длины n, каждая из которых является подперестановкой некоторой бесконечной перестановки, порожденной каким-то бинарным словом. Позднее в работе [29] С. Елизалде обобщил этот результат на алфавит произвольной
мощности q. В работе [46] М. А. Макаров вычислил комбинаторную
сложность бесконечных перестановок, порожденных хорошо известным
семейством слов Штурма. Комбинаторная сложность бесконечной перестановки, порожденной словом удвоения периода, была найдена М.
А. Макаровым в работе [47]. В работе [58] С. Уидмер нашел формулу
для комбинаторной сложности перестановки, порожденной словом ТуэМорса. Здесь стоит отметить, что из этой формулы следует, что аналог результата Ж. Кассеня о первой разности кусочно-линейной комбинаторной сложности не верен: комбинаторная сложность перестановки
Туэ-Морса — кусочно-линейная функция, и при этом ее первая разность
— тоже кусочно-линейная функция (а значит и неограниченная). Рассмотрим морфизм d такой, что d(0) = 00 и d(1) = 11. В работе [57] С.
Уидмер нашел связь между комбинаторной сложностью бесконечных
8
перестановок, порожденных словами ω и d(ω) соответственно, где ω —
произвольное бинарное равномерно рекуррентное слово. Также отметим, что понятие комбинаторной сложности бесконечной перестановки,
порожденной бесконечным словом (permutation complexity), было независимо введено в работе [5].
Как мы отмечали выше, линейный порядок <δω — это лексикографический порядок на множестве суффиксов слова ω, где δω — бесконечная
перестановка, порожденная словом ω. Поэтому изучение бесконечных
перестановок, порожденных бесконечными словами, — это, по сути, изучение свойств лексикографического порядка на множестве суффиксов
бесконечного слова. Здесь стоит отметить ряд статей [22,23], в которых
также изучались свойства лексикографического порядка на множестве
сдвигов бесконечного слова: в этих работах исследовались минимальные (с точки зрения лексикографического порядка) слова из орбиты
морфических слов.
Также отметим ряд работ, в которых изучались другие типы сложностей бесконечных перестановок: в статье [7] исследовали максимальную шаблонную сложность бесконечных перестановок, а в работах [45]
и [3] — арифметическую сложность.
Пятая глава диссертации относится к теории паттернов в перестановках, поэтому приведем небольшой обзор по этой тематике.
Теория паттернов в перестановках — раздел комбинаторики, изучающий конечные перестановки, избегающие подпоследовательностей
определенного типа. Основные книги по данной тематике — это монографии [13] и [36]. Современная теория паттернов в перестановках берет
начало с работ Д. Ротема [52], Д. Г. Роджерса [51] и Д. Кнута [40]. Систематическое же изучение паттернов в перестановках началось со статьи
Р. Симиона и Ф. Шмидта [53] 1985 года.
В теории паттернов в перестановках специалисты исследуют в
первую очередь следующие вопросы:
1. Для данного паттерна p найти число перестановок sn (p) длины n,
избегающих паттерн p. Либо найти рост последовательности sn (p).
2. Для двух паттернов p и q определить, выполняется ли равенство
sn (p) = sn (q). Если sn (p) = sn (q), то паттерны p и q называются эквивалентными по Вильфу. Обзначается эта эквивалентность
через p ∼W q.
9
Хорошо известно, что для любого классического паттерна p длины
3 sn (p) = Cn , где Cn — последовательность чисел Каталана (см. работу
МакМахона [44]). Поэтому возникает естественный вопрос — найти биекцию между множествами Sn (321) и Sn (132). Впервые такая биекция
была построена Д. Кнутом в работе [40]. Для этого им была построена
биекция между множеством Sn (321) и путями Дика (позже эта биекция
стала называться соответствием Робинсона-Шенстеда-Кнута), и между
множеством Sn (132) и путями Дика. Комбинируя эти биекции, он построил биекцию между множествами Sn (321) и Sn (132). Позднее появилось много других интересных биекций между множествами Sn (321) и
Sn (132). Текущий обзор по данной тематике можно найти в работе [21].
Д. Бэкелин в работе [10] доказал, что 1243 ∼W 2143. З. Станкова в
работах [55] и [56] доказала, что 1342 ∼W 2413 и 1234 ∼W 3214. Пусть
A = {1234, 1243, 2143, 3214}, B = {1342, 2413} и C = {1324}. Тогда с
помощью тривиальных биекций получаем, что любой паттерн длины 4
либо принадлежит одному из множеств A, B и C, либо эквивалентен
по Вильфу некоторому паттерну из этих множеств. Точные формулы
для sn (1234) и sn (1342) были получены И. Гесселем и М. Боной в работах [35] и [12] соответственно. Для последовательности sn (1324) точная
формула до сих пор неизвестна.
В 1980 году Р. Стэнли и Г. Вильф выдвинули следующую гипотезу:
для любого классического паттерна p существует константа c(p), зависящая только от p такая, что sn (p) ≤ c(p)n . В 2004 году А. Маркус и
Г. Тардош [48] доказали гипотезу Фюреди-Хайнала, из которой следует
справедливость гипотезы Стэнли-Вильфа.
В последние годы теория паттернов в перестановках активно изучается многими авторами. В частности, рассматриваются различные обобщения классических паттернов — сплошные [29], винкулярные [9], бивинкулярные [14], арифметические [8] и др. В отличие от классических
паттернов, для сплошных и винкулярных паттернов гипотеза СтэнлиВильфа не верна [36]. Из последних обобщений классических паттернов
стоит отметить ряд работ по мэш паттернам [15, 37, 38]. Мэш паттерны
были введены в работе [15] с целью выразить различные статитистики
на перестановках с помощью их линейной комбинации. В пятой главе данной диссертации мы продолжаем исследования мэш паттернов,
рассматривая их определенный подкласс.
Целью данной работы является исследование языков подперестано10
вок бесконечных перестановок, а также языков конечных перестановок,
избегающих подпоследовательностей с определенными свойствами.
Основные результаты диссертации.
1. Получена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками сравнимых равноблочных морфизмов. Впервые получена точная формула
для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками бесконечного семейства морфизмов. (Теорема 2.3)
2. Найдена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками обобщенного
морфизма Фибоначчи. Впервые получена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками неравноблочных морфизмов. (Теорема 3.2)
3. Доказано, что аналог известной гипотезы Стэнли–Вильфа для
классических паттернов в перестановках не выполняется для любого
рамочного паттерна длины более три, и отличного от паттернов 2143,
3142, 2413 и 3412. (Теорема 5.3)
Результаты 1 и 2 получены автором лично. Результат 3 получен в
неразделимом соавторстве с С. В. Августиновичем и С. В. Китаевым.
Научная новизна и значимость работы. Работа носит теоретический характер. Все основные результаты диссертации являются новыми. Результаты работы могут быть использованы при дальнейшем
исследовании комбинаторики слов и бесконечных перестановок. Также
результаты могут быть включены в спецкурсы для студентов и аспирантов, специализирующихся в области дискретной математики.
Методы исследования. В работе используются методы классической комбинаторики, комбинаторики слов, а также перечислительной
комбинаторики.
Апробация работы. Результаты диссертации докладывались на
Международной молодежной школе-конференции "Современные проблемы математики и ее приложений"(г. Екатеринбург, 2012, 2013), на
Международной конференции "Современные проблемы математики,
11
информатики и биоинформатики посвященной 100-летию со дня рождения члена-корреспондента АН СССР Алексея Андреевича Ляпунова
(г. Новосибирск, 2011), на Международной конференции по комбинаторике слов WORDS 2011 (г. Прага, 2011), на втором Международном
Русско–Финском симпозиуме по дискретной математике RuFiDiM 2012
(г. Турку, 2012), на Международной конференции по комбинаторике
слов WORDS 2013 (г. Турку, 2013).
Публикации. Результаты автора по теме диссертации опубликованы в шести работах [59–64], из них три статьи опубликованы в журналах из списка ВАК [59–61], три — в тезисах и трудах международных
конференций [62–64]. Результаты работы [60] получены в неразделимом
соавторстве с С. В. Августиновичем и С. В. Китаевым.
Структура и объем диссертации. Диссертация состоит из введения, 5 глав и списка литературы. Объем диссертации составляет 134
страницы. Список литературы содержит 70 наименований.
Содержание диссертации
Общая структура диссертации. Диссертация разбита на главы,
которые в свою очередь подразделяются на параграфы. Все утверждения (теоремы, леммы и следствия) имеют двойную нумерацию: первое
число — номер главы, второе — номер утверждения в текущей главе.
Во введении обосновывается актуальность темы исследования,
освещается степень ее разработки; изложены цели, методы исследования и основные результаты диссертации; отражены научная новизна и
значимость работы и данные об апробации. Также приведены сведения
о публикации результатов диссертации.
В первой главе приводятся основные сведения и определения, которые будут использоваться далее.
Во второй главе изучаются бесконечные перестановки, порожденные неподвижными точками морфизмов из класса Ql . Основной результат состоит в нахождении точной формулы для комбинаторной сложности этих перестановок. Таким образом, впервые получена точная фор12
мула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками бесконечного семейства морфизмов.
Пусть n ≥ l2 + 1. Тогда для числа n существует единственная пара
чисел k(n) и s(n) такая, что s(n) > 0, k(n) ∈ {l, ..., l2 − 1} и k(n)ls(n) <
n ≤ (k(n) + 1)ls(n) . Число n − k(n)ls(n) обозначим через r(n). Заметим,
что n = k(n)ls(n) + r(n) и r(n) ∈ [1, ls(n) ]. Основным результатом второй
главы является следующая теорема:
Теорема 2.3. Пусть ω — неподвижная точка морфизма ϕ, где ϕ ∈
Ql и n ≥ l2 + 1. Тогда комбинаторная сложность перестановки δω
вычисляется следующим образом:
λ(n) = (r(n) − 1)µ(k(n) + 2) + (ls(n) − r(n) + 1)χ(k(n) + 1) − β(k(n) + 1)
для r(n) > 1 и
λ(n) = ls(n) χ(k(n) + 1) − α(k(n))
для r(n) = 1.
Все функции µ(m), χ(m), β(m) и α(m) однозначно определяются с
помощью семейства множеств Hu , где u — произвольное подслово слова
ω длины m или m + 1.
В третьей главе изучаются бесконечные перестановки, порожденные неподвижными точками морфизмов вида ϕ(0) = 01k , ϕ(1) = 0 для
k ≥ 2. Основной результат состоит в нахождении точной формулы для
комбинаторной сложности этих перестановок. Таким образом, впервые
получена точная формула для комбинаторной сложности бесконечных
перестановок, порожденных неподвижными точками неравноблочных
морфизмов.
√
√
1− 1+4k
— собственные значения матПусть λ1 = 1+ 21+4k
2
и λ2 =
√
√
1 1
(k+ 1+ 21+4k )x+ 1+ 21+4k y
√
рицы A =
, c1 (x, y) =
и c2 (x, y) =
1+4k
k 0
√
(
1+4k−1
−k)x+
2
√
1+4k
√
1+4k−1
y
2
. Рассмотрим последовательности as = c1 (k +
+ c2 (2, k)λs−1
+1 и
1, k 2 )λs1 + c2 (k + 1, k 2 )λs2 + 1, bs = c1 (2, k)λs−1
1
2
s−1
s−1
ms = c1 (1, 0)λ1 + c2 (1, 0)λ2 .
Основным результатом третьей главы является следующая теорема:
Теорема 3.2. Пусть ω — неподвижная точка морфизма ϕ, где ϕ(0) =
01k , ϕ(1) = 0, n > k 2 + k + 1, k > 2 и s ≥ 2. Тогда комбинаторная сложность перестановки δω может быть вычислена следующим образом:
13
1. При as < n < bs+3 имеем λ(n) = 2n + M1 λs+1
+ M2 λs+1
+ W1 , где
1
2
1
2
2
M1 = λ1 −1 (c1 (1 + k, k ) + c1 (1, 0)λ1 − c1 (1, 1)λ1 ), M2 = λ21−1 (c2 (1 +
k, k 2 ) + c2 (1, 0)λ2 − c2 (1, 1)λ22 ) и W1 — некоторая константа, зависящая от k;
2. При bs+3 ≤ n ≤ as+1 имеем λ(n) = 3n − as+1 + M1 λs+2
+
1
M2 λs+2
+ W2 , где M1 = λ11−1 (c1 (1 + k, k 2 ) + c1 (1, 0)λ1 − c1 (1, 1)λ21 ),
2
M2 = λ21−1 (c2 (1 + k, k 2 ) + c2 (1, 0)λ2 − c2 (1, 1)λ22 ) и W2 — некоторая
константа, зависящая от k.
Для k = 2 доказывается следующий результат: при as < n < bs+2
имеем λ(n) = n + N1 λs+1
+ N2 λs+1
+ Q1 , где N1 = λ11−1 (c1 (1 + k, k 2 ) +
1
2
1
c1 (1, 0) − c1 (1, 1)λ1 ), N2 = λ2 −1 (c2 (1 + k, k 2 ) + c2 (1, 0) − c2 (1, 1)λ2 ) и Q1
— некоторая константа, зависящая от k; при bs+2 ≤ n ≤ as+1 имеем
λ(n) = 2n − as+1 + N1 λs+2
+ N2 λs+2
+ Q2 , где N1 = λ11−1 (c1 (1 + k, k 2 ) +
1
2
c1 (1, 0) − c1 (1, 1)λ1 ), N2 = λ21−1 (c2 (1 + k, k 2 ) + c2 (1, 0) − c2 (1, 1)λ1 ) и Q2
— некоторая константа, зависящая от k.
В четвертой главе вводится новый класс бесконечных перестановок, которые конструируются как некоторый аналог неподвижных точек морфизмов для слов. Основной результат состоит в нахождении
точной формулы для комбинаторной сложности этих перестановок.
Отметим, что результаты четвертой главы не выносятся на защиту и
не входят в основные результаты диссертации. Тем не менее, использованный в четвертой главе новый способ порождения бесконечных перестановок представляет большой интерес для дальнейших исследований.
В пятой главе вводится понятие рамочного мэш паттерна и изучаются языки конечных перестановок, избегающих эти паттерны. Мэш
паттерном называется пара p = (π, R), где π — некоторая перестановка длины k и R ∈ [0, k] × [0, k]. Пусть π = π1 π2 . . . πn — произвольная
перестановка длины n. Множество точек плоскости G(π) = {(i, πi )|i =
1, . . . , n} будем называть диаграммой перестановки π. Вхождением мэш
паттерна p в перестановку τ называется подмножество точек ω множества G(τ ) такое, что существуют две сохраняющие порядок инъекции
α, β : [1, k] → [1, n] такие, что выполнены два следующих условия:
1. ω = {(α(i), β(j)) : (i, j) ∈ G(π)}.
14
2. Определим множество Ri,j = [α(i) + 1, α(i + 1) − 1] × [β(j) + 1, β(j +
1) − 1] для i, j ∈ [0, k], где α(0) = β(0) = 0 и α(k + 1) = β(k + 1) =
n + 1. Тогда если (i, j) ∈ R, то Ri,j ∩ G(τ ) = ∅.
Мэш паттерн p = (x, R), для которого R = [1, k − 1] × [1, k − 1], будем
называть рамочным мэш паттерном или просто рамочным паттерном. Обозначим рамочный паттерн p = (x, R) через x .
Доказывается, что аналог известной гипотезы Стэнли–Вильфа не
выполняется для любого рамочного паттерна длины более три, и отличного от паттернов 2143 , 3142 , 2413 и 3412 . Также доказывается,
что аналог гипотезы Стэнли–Вильфа не выполняется для паттернов
123 и 321 :
Теорема 5.3. Пусть p — произвольный рамочный паттерн длины k ≥ 4, который не принадлежит
множеству
{ 2143 , 3142 , 2413 , 3412 }. Тогда sn ( p ) > b n2 c !.
Кроме того, в пятой главе найдены производящиие функции для
последовательностей sn (a, 123 ), где a — произвольный классический
паттерн длины три. В частности, доказана следующая теорема:
Теорема 5.5. Последовательность (sn (231, 123 ))n≥0 с точностью до
сдвига совпадает с последовательностью обобщенных чисел Каталана
(см. последовательность A004148 в OEIS [54]). Производящая функция
последовательности sn (231, 123 ) равна
√
1 − x − x2 − 1 − 2x − x2 − 2x3 + x4
.
2x3
Благодарности
Автор выражает благодарность своему научному руководителю Денису Станиславовичу Кротову за неоценимую помощь во время работы
над диссертацией. Автор благодарит А. Э. Фрид, С. В. Августиновича и
С. В. Китаева за интересные задачи и полезные обсуждения. Автор признателен всем сотрудникам лаборатории совершенных комбинаторных
структур ИМ СО РАН за творческую атмосферу и полученные знания в
процессе обучения в аспирантуре. Также автор благодарит своего брата
В. А. Валюженича, взявшего на себя труд прочитать первоначальный
вариант черновика диссертации.
15
Литература
[1] Августинович С. В. Число различных подслов заданной длины в
последовательности Морса–Хедлунда // Сибирский журнал исследования операций. 1994. Т. 1, №2. С. 3-7.
[2] Фрид А. Э. О комбинаторных свойствах D0L слов. Дисс. канд. физ.мат. наук: 01.01.09. — Новосибирск, 2000. — 104 с.
[3] Макаров М. Антимонотонные перестановки // Сибирские электронные математические известия. 2012. Т. 9. С. 346-359.
[4] Allouche J. -P., Shallit J. Automatic sequences — theory, applications,
generalizations. Cambridge University Press, 2003.
[5] Amigó J. M. Permutation complexity in dynamical systems. Springer
Series in Synergetics, Springer-Verlag, Berlin, 2010.
[6] Avgustinovich S. V., Frid A. E. On bispecial words and subword
complexity of D0L sequences // in: Proceedings of SETA’98, DMTCS
series. Springer. 1999, p. 191-204.
[7] Avgustinovich S. V., Frid A. E, Kamae T., Salimov P. Infinite
permutations of lowest maximal pattern complexity // Theoretical
Computer Science. 2011. Vol. 412. p. 2911-2921.
[8] Avgustinovich S. V., Kitaev S. V., Valyuzhenich A. A. Crucial and
bicrucial permutations with respect to arithmetic monotone patterns
// Sib. Elektron. Mat. Izv. 2012. Vol. 9. p. 660-671.
[9] Babson E., Steingrímsson E. Generalized permutation patterns and a
classification of the Mahonian statistics // Sém. Lothar. Combin. 2000.
Vol. 44. Art. B44b, 18pp. (electronic).
[10] Backelin J., West J., Xin G. Wilf-equivalence for singleton classes //
Advances in Applied Mathematics. 2007. Vol. 38, no. 2. p. 133-148.
[11] Berstel J. Sturmian and episturmian words (a survey of some recent
results). // In S. Bozapalidis and G. Rahonis, editors, CAI 2007, Vol.
4728 of Lecture Notes in Computer Science, Springer-Verlag. 2007. p.
23-47.
16
[12] Bóna M. Exact enumeration of 1342-avoiding permutations: a close link
with labeled trees and planar maps // J. Combin. Theory Ser. A. 1997.
Vol. 80. no. 2. p. 257-272.
[13] Bóna M. Combinatorics of permutations. Discrete Mathematics and
its Applications (Boca Raton). Chapman Hall/CRC, Boca Raton, FL,
2004. With a foreword by Richard Stanley.
[14] Bousquet-Mélou M., Claesson A., Dukes M., Kitaev S. (2 + 2)-free
posets, ascent sequences and pattern avoiding permutations // J.
Combin. Theory Ser. A. 2010. Vol. 117, no. 7. p. 884–909.
[15] Brändén P., Claesson A. Mesh patterns and the expansion of
permutation statistics as sums of permutation patterns // Electronic
Journal of Combinatorics. 2011. Vol. 18, no. 2. #P5, 14pp.
[16] Brlek S. Enumeration of factors in the Thue-Morse word // Discrete
Applied Mathematics. 1989. Vol. 24. p. 83-96.
[17] Cassaigne J., Nicolas F. Factor Complexity in Combinatorics,
Automata and Number Theory, V. Berthé and M. Rigo (eds.),
Cambridge Unicersity Press, Cambridge, 2010.
[18] Cassaigne J. An algorithm to test if a given circular HD0L-language
avoids a pattern // IFIP World Computer Congress’94. Elsevier
(North-Holland). 1994. Vol 1. p. 459-464.
[19] Cassaigne J. Complexité et facteurs spéciaux // Bull. Belg. Math. Soc.
1997. Vol. 4. p. 67-88.
[20] Cassaigne J. Special factors of sequences with linear subword
complexity // Developments of Language Theory II. Singapore: World
Sci.Publishing. 1996. p. 25-34.
[21] Claesson A., Kitaev S. Classification of bijections between 321- and
132- avoiding permutations // Sém. Lothar. Combin. 2008. Vol. 60.
Art. B60d, 30.
[22] Currie J. Lexicographically least words in the orbit closure of the
Rudin–Shapiro word // Theoretical Computer Science. 2011. Vol. 412.
p. 4742–4746.
[23] Currie J., Rampersad N., Saari K., Zamboni L. Extremal words in
morphic subshifts // Discrete Mathematics. 2014. Vol. 322. 53-60.
17
[24] Davis J., Entringer R., Graham R., Simmons G. On permutations
containing no long arithmetic progressions // Acta Arithmetica. 1977.
Vol. 34. p. 81-90.
[25] Durand F. A characterization of substitutive sequences using return
words // Discrete Mathematics. 1998. Vol. 179. p. 89–101.
[26] Durand F., Leroy J., Richomme G. Do the Properties of an S-adic
Representation Determine Factor Complexity // Journal of Integer
Sequences. 2013. Vol. 16, no. 2:Art. 13.2.6, 30.
[27] Elizalde S. The number of permutations realized by a shift // SIAM J.
Discrete Math. 2009. Vol. 23. p. 765-786.
[28] Ehrenfeucht A., Lee K. P., Rozenberg G. Subword complexities
of various classes of deterministic developmental languages without
interactions // Theoretical Computer Science. 1975. Vol. 1. p. 59-75.
[29] Elizalde S., Noy M. Consecutive patterns in permutations. Advances
in Applied Mathematics. 2003. Vol. 30, no. (1-2). p. 110-125.
[30] Ferenczi S. Complexity of sequences and dynamical systems // Discrete
Math. 1999, Vol. 206, p. 145-154.
[31] Frid A. Infinite permutations vs. infinite words // Eletronic
Proceedings in Theoretical Computer Science. 2011. Vol. 63. p. 13-19.
[32] Frid A. E. Fine and Wilf’s theorem for permutations // Siberian
Electronic Mathematical Reports. 2012. Vol. 9. p. 377-381.
[33] Frid A. E. On uniform D0L words // STACS’98, Lect. Notes Comp.
Sci. 1998. Vol. 1373. p. 544-554.
[34] Fon-Der-Flaass D. G. and Frid A. E. On periodicity and low complexity
of infinite permutations // European Journal of Combinatorics. 2007.
Vol. 28, no. 8. p. 2106-2114.
[35] Gessel I. M. Symmetric functions and P-recursiveness // J. Combin.
Theory Ser. A. 1990. Vol. 53, no. 2. p. 257-285.
[36] Kitaev S. Patterns in permutations and words, Springer-Verlag, 2011.
[37] Kitaev S., Liese J. Harmonic numbers, Catalan triangle and mesh
patterns // Discrete Mathematics. 2013. Vol. 313. p. 1515-1531.
[38] Kitaev S., Remmel J. Quadrant marked mesh patterns // Journal of
Integer Sequences. 2012. Vol. 15. Article 12.4.7, 29pp.
18
[39] Klouda K. Bispecial factors in circular non-pushy D0L languages //
Theoretical Computer Science. 2012. Vol. 445. p. 63-74.
[40] Knuth D. E. The art of computer programming. Volume 1,
Fundamental Algorithms. Addison-Wesley, Reading, second edition,
1975. Addison-Wesley Series in Computer Science and Information
Processing.
[41] de Luca A. and Varricchio S. Some combinatorial properties of the
Thue-Morse sequence and a problem in semigroups // Theoretical
Computer Science. 1989. Vol. 63. p. 333-348.
[42] Leroy J. An S-adic characterization of minimal subshifts with first
difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 // Discrete
Mathematics and Theoretical Computer Science. 2014. Vol. 16, no. 1.
p. 233-286.
[43] Lothaire, M. Algebraic Combinatorics on Words. // V. 90 of
Encyclopedia of Mathematics and Its Applications. Cambridge
University Press, 2002.
[44] MacMahon P. A. Combinatory analysis. Vol. I, II (bound in one
volume). Dover Phoenix Editions. Dover, Mineola, 2004. Reprint of An
introduction to combinatory analysis (1920) and Combinatory analysis.
Vol. I, II (1915,1916).
[45] Makarov M. A. On permutations generated by infinite binary words //
Sib. Elektron. Mat. Izv. 2006. Vol. 3. p. 304-311 (in Russian).
[46] Makarov M. A. On the permutations generated by the Sturmian words
// Sib. Math. J. 2009. Vol. 50, no. 4. p. 674-680.
[47] Makarov M. A. On the infinite permutation generated by the period
doubling word // European Journal of Combinatorics. 2010. Vol. 31,
no. 1. p. 368-378.
[48] Marcus A., Tardos G. Excluded permutation matrices and the StanleyWilf conjecture // J. Combin. Theory Ser. A. 2004. Vol. 107, no. 1,
153–160.
[49] Morse M., Hedlund G. A. Symbolic Dynamics II: Sturmian Trajectories
// Amer. J. Math. 1940. Vol. 61. p. 1–42.
19
[50] Pansiot J.-J. Complexité des facteurs des mots infinis enegendrés par
morphismes itérés // in ICALP ’84, Lecture Notes in Computer Science
172, Springer-Verlag (1984), p. 380-389.
[51] Rogers D. G. Ascending sequences in permutations // Discrete
Mathematics. 1978. Vol. 22, no. 1. p. 35-40.
[52] Rotem D. On a correspondence between binary trees and a certain type
of permutation // Information Processing Letters. 1975/76. Vol. 4, no.
3. p. 58-61.
[53] Simion R., Schmidt F. W. Restricted permutations // European
Journal of Combinatorics. 1985. Vol. 6, no. 4. p. 383-406.
[54] N.
J.
A.
Sloane,
The
on-line
encyclopedia
integer
sequences,
published
electronically
at
http://www.research.att.com/˜njas/sequences/.
of
[55] Stankova Z. E. Forbidden subsequences // Discrete Mathematics. 1994.
Vol. 132, no. (1-3). p. 291-316.
[56] Stankova Z. E. Classification of forbidden subsequences of length 4 //
European Journal of Combinatorics. 1996. Vol. 17, no. 5. p. 501-517.
[57] Widmer S. Permutation Complexity of the Thue-Morse Word //
Advances in Applied Mathematics. 2011. Vol. 47, no. 2. p. 309-329.
[58] Widmer S. Permutation complexity related to the letter doubling map
// Electronic Proceedings in Theoretical Computer Science. 2011. Vol.
63. pp. 265-276.
Публикации автора по теме диссертации
[59] Валюженич А. О перестановочной сложности неподвижных точек
некоторых неравноблочных бинарных морфизмов // Сибирские
электронные математические известия. 2015. Т. 12. С. 64-79.
[60] Avgustinovich S., Kitaev S., Valyuzhenich A. Avoidance of boxed mesh
patterns on permutations // Discrete Applied Mathematics. 2013. Vol.
161. p. 43–51.
20
[61] Valyuzhenich A. On permutation complexity of fixed points of some
uniform binary morphisms // Discrete Mathematics and Theoretical
Computer Science. 2014. Vol.16, no. 3. p. 95-128.
Публикации в тезисах и трудах конференций
[62] Valyuzhenich A. Permutation complexity of the fixed points of some
uniform binary morphisms // Electronic Proceedings in Theoretical
Computer Science. 2011. Vol. 63. p. 257-264.
[63] Valyuzhenich A. Permutation complexity of the fixed points of
comparable morphisms // Proc. 2nd Russian Finnish Symposium on
Discrete Mathematics. 2012. Vol. 17 of TUCS Lecture Notes. Turku.
p. 184–186.
[64] Valyuzhenich A. On factor complexity of infinite permutations // Local
Proc. 9th International Conference in Combinatorics on Words. 2013.
Vol. 20 of TUCS Lecture Notes. Turku. p. 97–108.
21
Документ
Категория
Без категории
Просмотров
1
Размер файла
363 Кб
Теги
языков, факторный, комбинаторные, свойства, перестановок
1/--страниц
Пожаловаться на содержимое документа