Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств

Батуева, Цындыма Чимит-Доржиевна

Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Батуева, Цындыма Чимит-Доржиевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств»

Автореферат диссертации на тему "Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств"

4859186

На правах рукописи

БАТУЕВА Цындыма Чимит-Доржиевна

ПРИМЕНЕНИЕ АЛГЕБРАИЧЕСКИХ МЕТОДОВ В РЕШЕНИИ НЕКОТОРЫХ ВОПРОСОВ СЛОЖНОСТИ КОМБИНАТОРНОЙ ТЕОРИИ СЛОВ И ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

у \ / 10 НОЯ 2011

/пПГ

Новосибирск - 2011

4859186

Работа выполнена в Новосибирском государственном университете

Научные руководители: доктор физико-математических наук, Семенова Марина Владимировна кандидат физико-математических наук, Фрид Анна Эдуардовна

Официальные оппоненты:

доктор физико-математических наук, профессор, Мартынов Леонид Матвеевич кандидат физико-математических наук, Августинович Сергей Владимирович

Ведущая организация:

Уральский федеральный университет

Защита состоится 30 ноября 2011 г. в 16 часов на заседании диссертационного совета Д 003.015.01 при Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук ио адресу: пр. Академика Коптюга 4, г. Новосибирск 630090.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан " октября 2011 г. "Ученый секретарь

диссертационного совета Д 003.015.01,

д.ф.-м.н.

Ю.В. Шамардин

Общая характеристика работы Актуальность темы.

Настоящая работа находится на стыке дискретной математики, универсальной алгебры и теории решеток. В ней с использованием комбинаторных и алгебраических методов, а также частично методов теории моделей изучаются классические комбинаторные объекты, такие как формальные языки и частично упорядоченные множества. Целью исследований, результаты которых изложены здесь, было изучение алгебраических и комбинаторных свойств, во-первых, двумерных слов над конечными алфавитами и, во-вторых, частично упорядоченных множеств, а также изучение сложности строения некоторых связанных с ними производных конструкций. Вопросы, изучаемые в настоящей диссертации, естественным образом возникли при изучении формальных языков и частично упорядоченных множеств, соответственно.

Задача построения двумерных слов небольшой комбинаторной сложности, а также получение точных формул для этой сложности являются актуальными проблемами теории формальных языков. Существуют определенные границы, за которыми всякое двумерное слово становится периодическим. Изучение слов, лежащих на этой границе и в непосредственной близости от нее, может иметь самые неожиданные следствия и приложения в таких областях, как теория кодирования, кристаллография, теория фракталов и др.

Рассмотрим бесконечное одномерное слово v = f(l)u(2)y(3) над конечным алфавитом Е. Подсловом слова v называется слово вида v(i)v(i + 1).. .v(i + n - 1) для некоторых г,п е N. Комбинаторная сложность р(п) слова v, введенная Эренфойхтом, Ли и Розенбергом [9] в 1975 году, равна числу подслов слова v длины п. Известно, что одномерное слово непериодично тогда и только тогда, когда его комбинаторная сложность р(п) имеет рост не меньше n + 1, п £ N. Слова с комбинаторной сложностью p(n) = n + 1, то есть непериодичные слова с минимальной комбинаторной сложностью, называются словами Штурма [23, глава 3].

Бесконечным двумерным словом ги называется функция N х

N —► Е:

ги(2,1) и>(2,2) и)( 2,3) ... го(1,1) ад(1,2) ш(1,3) ...

Для двумерных бесконечных слов комбинаторная сложность р(к, I) определяется как количество прямоугольных подслов длины к и высоты I. Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива:

Гипотеза Нива [27] Если функция комбинаторной сложности Рхи(к,1) двумерного слова и) удовлетворяет условию рш(к,1) ^ Ы для некоторой пары целых чисел (к,1), то и> имеет по крайней мере один вектор периодичности.

К настоящему времени были доказаны некоторые более слабые формы этой гипотезы, см. [10], [17]. Рассматривались также двумерные аналоги слов Штурма со сложностью, равной Ы + 1, см. [5].

Комбинаторная сложность имеет много модификаций. Упом'я-нем такие как (¿-сложность, введенная Иваньи [16] в 1987 году, па-линдромная сложность, введенная Аллушем, Бааком, Кассенем и Дамаником [1] в 2002 году, модифицированная сложность Нака-симы и других [26], веденная в 2003 году, шаблонная сложность, введенная Рестиво и Салеми [28] в 2002 году.

Арифметическая сложность, введенная Августиновичем, Фрид и Фон-Дер-Флаассом [4] в 2003 году, является модификацией комбинаторной сложности. Арифметической подпоследовательностью слова V называется последовательность ь(к)и(к + с1)... у(к + пй)... с началом в точке к и шагом й. Всякое подслово арифметической подпоследовательности слова у называется арифметическим подсловом слова V. Множество всех арифметических подслов слова у называется его арифметическим замыканием. Арифметической сложностью слова V называется функция /(п), равная числу всех его различных арифметических подслов длины п.

Арифметическая сложность для непериодического слова может расти как экспоненциально [12], так и линейно. При этом известна

характеризация равномерно рекуррентных слов с линейной арифметической сложностью [13]. Кроме того, известны примеры слов, арифметическая сложность которых растет быстрее, чем любой полином, но медленее, чем с" для некоторого с > 1 [15], а также как 6(па), где а — корень некоторого трансцендентного уравнения [7].

Максимальная шаблонная сложность, введенная Камаэ и Зам-бони [21] в 2002 году, является еще одной модификацией комбинаторной сложности. Как и для обычной комбинаторной сложности одним из направлений изучения сложностей является установление связи между периодичностью слова и значением функции сложности. Наименьшая максимальная шаблонная сложность непереоди-ческого слова равна 2к [21, Теорема 1]. Для двумерных слов Камаэ, Pao и Сюэ [18] было доказано, что двумерное слово периодично по двум неколлинеарным направлениям тогда и только тогда, когда оно сильно 2-рекуррентно и его максимальная шаблонная сложность не превосходит 2к — 1 для некоторого к. В работе Камаэ и Сюэ [19] был предложен один пример такого двумерного слова, но полное описание всех слов с максимальной шаблонной сложностью, равной 2к, еще не найдено ни для двумерного, ни для одномерного случаев.

Рассмотрим некоторый выделенный символ о ^ Е и одномерное слово и € (£ Uo)u. Пусть Т°(и) — и и пусть Тг+1(ъ>) получается из Тг(и) последовательной заменой всех вхождений символа о на символы из слова и. Предельная последовательность

Г11» = lim T(v)

г—>оо

называется одномерным словом Теплица [6]. Комбинаторная сложность и периодичность таких слов ранее уже исследовались, например, в работах [6] и [22]. Их арифметическая сложность исследовалась в [3] и [4]; кроме того, оказывается, что слова Тёплица особого вида — это единственные равномерно рекуррентные слова с линейной арифметической сложностью [13].

Под позицией будем понимать пару неотрицательных целых чисел и подразумевать координаты некоторого символа двумерного слова. Пусть натуральные числа m,l ^ 2. Позиция (i,j) € N2 называется s-ключевой, если s — максимальное натуральное число такое, что ms и ls делят г и j соответственно. Позиция называется

ключевой, если она является ¿-ключевой для некоторого в > 0.

Построим двумерное бесконечное слово а(ш,0- Сначала заполним нулями все неключевые позиции. Затем все в-ключевые позиции для нечетного 5 заполняются единицами, а все в-ключевые позиции для четного й заполняются нулями.

0 о 0 о 0 о 0 о

0 0000000

0 о 0 о 0 о 0 о

0 0000000

0 о 0 о 0 о 0 о

0 0000000

0 10 10 10 1

0 0000000

-►О 1 0 0 0 1 0 0

О 0 000000

0 10 10 10 1

О 0000000

Предельное двумерное слово называется элементарным словом Теплица.

В данной работе впервые рассматривается арифметическая сложность двумерных слов. Описаны слова арифметического замыкания класса элементарных слов Тёплица. Для некоторых из этих слов посчитана арифметическая сложность. Построена бесконечная двухпараметрическая серия двумерных слов, имеющих максимальную шаблонную сложность 2к.

Другим объектом исследования являются частично упорядоченные множества и связанные с ними производные решетки. Частично упорядоченные множества являются классическим объектом изучения в различных областях дискретной математики, универсальной алгебры, теории решеток, а также служат вспомогательным инструментом исследований и во многих других областях математики (например, в математической логике, теории моделей, теоретическом программировании и других). В настоящей работе изучаются решетки выпуклых подмножеств, а также решетки идеалов частично упорядоченных множеств. Результаты, полученные в настоящей работе, продолжают исследования ряда авторов и касаются двух типов производных решеток, связанных с частично упорядоченными множествами, — решеток выпуклых подмножеств и решеток идеалов.

Решетки выпуклых подмножеств частично упорядоченных множеств служат выразительным примером выпуклых геометрий, см. монографию Горбунова [30] и обзорные работы Семеновой [35, 31]. Эти решетки интенсивно изучались рядом авторов, см. работы [32, 36, 37, 38, 39, 40, 41]. В частности, в работе Биркгофа и Беннет [32] была получена характеризация класса решеток, изоморфных таким решеткам, откуда следует полудистрибутивность вверх решеток выпуклых подмножеств. В работе Семеновой и Замойской-Дженио [40] были описаны решетки, изоморфные решеткам выпуклых подмножеств частично упорядоченных множеств, являющихся лесами. В работе Семеновой и Верунга [36] было показано, что класс решеток, вложимых в решетки выпуклых подмножеств частично упорядоченных множеств, является конечно базируемым многообразием, а также был найден конкретный базис тождеств этого многообразия. Далее, в работах Семеновой, Верунга и Замойской-Дженио [37, 38, 39, 41] было получено описание классов решеток (конечных решеток), вложимых в решетки выпуклых подмножеств для различных конкретных классов частично упорядоченных множеств (в частности, для класса частично упорядоченных множеств конечной длины в [37]). Очень часто оказывалось, что эти классы решеток являются многообразиями, а для конечных решеток — псевдомногообразиями.

В настоящей работе описаны решетки, изоморфные решеткам выпуклых подмножеств частично упорядоченных множеств конечной длины. Кроме того, дана характеризация на языке предикатов первого порядка класса конечных решеток, изоморфных решеткам выпуклых подмножеств п-арных деревьев для любого целого п > 0.

пуклых подмножеств произвольного дерева в решетку выпуклых подмножеств п-арного дерева для некоторого п > 0. Один из результатов настоящей работы показывает, что ответ на этот вопрос в общем случае отрицателен. А именно, мы показзываем, что классы решеток, вложимых в решетки выпуклых подмножеств п-арных деревьев и изоморфных таким решеткам, различны для различных п > 0.

Решетки идеалов также являются примером решеток замыканий. Понятие идеала в решетках является классическим и к настоящему времени хорошо изучено. Хорошо известно, например, что решетка идеалов любой решетки удовлетворяет тем же тождествам, что и исходная решетка, см. [44, лемма 8]. Некоторые понятия идеала в частично упорядоченном множестве, обобщающие понятие идеала в решетке, были введены в работах Халаша и других [45, 47]. Мы вводим общее понятие идеала в частично упорядоченном множестве, связанное с его пополнением, и описываем некоторые свойства таких идеалов; подробнее см. ниже. Например, мы показываем, что любой идеал в дистрибутивном частично упорядоченном множестве является пересечением простых идеалов, его содержащих, что является обобщением классического результата для дистрибутивных решеток.

В работах Корниша [42, 43] были описаны дистрибутивные решетки с наименьшим элементом, в которых каждый простой идеал содержит не более п минимальных простых идеалов для произвольного фиксированного п > 0. Такие решетки были названы Корнишем п-нормалъными. Мы обобщаем это описание на случай частично упорядоченных множеств, которые являются нижними полурешетками с наименьшим элементом.

Цель работы.

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

Основные результаты.

1. Найдена арифметическая сложность подкласса двумерных элементарных слов Теплица.

2. Расширена серия примеров двумерных слов с минимально возможным значением максимальной шаблонной сложности среди сильно 2-рекуррентных слов.

3. Дано описание решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств конечной длины.

4. Дана характеризация на языке предикатов первого порядка класса конечных решеток, изоморфных решеткам выпуклых подмножеств п-арных лесов для любого п > 0.

Основные методы.

В диссертации использованы комбинаторные методы дискретного анализа, методы универсальной алгебры и теории решеток, а также, частично, методы теории моделей.

Научная новизна.

Все результаты, представленные в диссертации, являются новыми.

Теоретическая и практическая ценность.

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

Апробация результатов работы.

Результаты работы докладывались на следующих международных конференциях: Международной научной студенческой конфереи-

ции в Новосибирске в 2008, 2009, 2011 годах, XVII Международной школе-семинаре "Синтез и сложность управляющих систем" им. академика О. Б. Лупанова в Новосибирске в 2008 году, IV Международной конференции "Математика, ее приложения и математическое образование" на оз. Байкал в 2011 году, Международной конференции "Мальцевские чтения" в Новосибирске в 2011 году. Результаты докладывались на семинарах "Теория кодирования", "Дискретный анализ" и "Теория моделей" Института математики им. С. Л. Соболева СО РАН и Новосибирского государственного университета, а так же на семинаре "Алгебраические системы" Уральского федерального университета. Результаты диссертации были отмечены дипломом Международной научной студенческой конференции (2009 год). Работа выполнена при поддержке гранта Президента РФ "Молодые доктора наук" МД-2587.2010.1.

Публикации.

Основные результаты диссертации получены автором самостоятельно и опубликованы в журналах, входящих в перечень ВАК ведущих рецензируемых научных журналов и изданий, где должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук [49]-[51]. Результаты работы [52] получены автором совместно с М. В. Семеновой, не входят в список основных результатов настоящей диссертации и включены в неё для полноты изложения. Работы [53]-[57] являются тезисами докладов автора на различных конференциях.

Структура и объем диссертации.

Диссертация состоит из введения, двух глав и списка литературы, который содержит 57 наименований. Объем диссертации составляет 88 страниц, включая 2 рисунка.

Содержание диссертации

Во введении обосновывается актуальность темы диссертации, приводится краткий обзор полученных результатов. Коротко из-

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

Первая глава диссертации посвящена арифметической сложности и максимальной шаблонной сложности двумерных элементарных слов Теплица.

Неподвижной точкой двумерного морфизма ip называется двумерное бесконечное слово w, удовлетворяющее равенству <p(w) — w. В диссертации исследуются неподвижные точки морфизма

О ... О 1 0 ... О О

V(m,0 :0 —> 1 —

О ... О 0 0 ... О О

где 7П,! ^ 2 и тп — ширина, а / — высота образа символа. Слова а(ТО)г) также являются элементарными словами Тёплица.

Арифметической подпоследовательностью двумерного бесконечного слова w называется слово w(x, y)w(x + г, у + сГ)... и>(х + пг, у + nd)... с началом в позиции (х,у) и шагом (г, d). Арифметической сложностью двумерного бесконечного слова w называется функция fw{n), равная числу различных подслов длины п всех его арифметических подпоследовательностей.

Первый основной результат этой диссертации сформулирован в следующей теореме.

Теорема 1.1.19 Пусть т — простое число. Тогда арифметическая слоо/спость двумерного элементарного слова Тёплица растет линейно.

Для доказательства этой теоремы предварительно доказываются десять вспомогательных лемм (леммы 1.1.6, 1.1.8, 1.1.9-1.1.15, 1.1.17).

Операция инверсии заменяет в слове и символы 1 на 0 и 0 на 1. Полученное слово обозначается через и. Прореживание vUlu одномерного слова v = V\V2 ■. • vn одномерным конечным словом и

получается путем включния слова и между каждыми двумя соседними символами слова и, то есть уШи = у\иуъи... иуп. Введем функцию Т>п(и) = г1Ш0п_1, где п € К\{0}. Следующая теорема дает полное описание слов арифметического замыкания двумерного элеметарного слова Теплица <х-{т,1) Для произвольных значений т и I.

Теорема 1.1.21 Пусть т,1 > 2. Слово и принадлежит арифметическому замыканию двумерного элементарного слова Теплица а(т I) тогда и только тогда, когда и или и являются подсловами одного из следующих слов:

(О (0П) для некоторых г, п € К;

(II) Т>гт(у), где V — подслово слова, полученного способом

(III) Т>\(у), где V — подслово слова, полученного способом (¿);

(IV) Т>гр(у), где V — подслово слова, полученного способом (¿), (11) или (ш), р — делитель чисел нок(т,1), т или I соответственно.

В этой главе также рассматривается максимальная шаблонная сложность двумерных элементарных слов Тёплица.

Конечное множество т С Ъ2 мощности к, содержащее пару (0,0), называется к-шаблоном. Функция т —► Е называется т-словом. Некоторое т-слово Ъ называется т-подсловом двумерного слова -и), если существует такая пара (ж,у), что ш[{х.у) + т] = Ь. Пусть обозначает множество всех т-подслов слова V). Мак-

симальной шаблонной сложностью слова гу называется функция Рщ(/г), определенная следующим образом:

рЦк) = тах{#^(т) | к е К, г - /с-шаблон}.

шаблонная сложность строго меньше 2к для некоторого к G N, и слово является строго 2-рекуррентным, см. [18]. Таким образом, 2к — это минимум максимальной шаблонной сложности для строго 2-рекуррентных слов, не являющихся сильно периодическими. До сих пор был известен только один пример таких слов, см. [19].

Второй основной результат этой диссертации, сформулированн-ный в следующей теореме, предлагает серию таких слов.

Теорема 1.2.5 Для произвольных m,l ^ 2 максимальная шаблонная сложность двумерного элементарного слова Теплица равна 2к для всех к ^ 1.

Для доказательства теоремы 1.2.5 были доказаны две вспомогательные леммы (леммы 1.2.6 и 1.2.7).

Во второй главе исследуются решетки выпуклых подмножеств частично упорядоченных множеств, обладающих определенными свойствами, а также рассматривается общее понятие идеала в частично упорядоченных множествах.

Пусть (Р, <) — частично упорядоченное множество. Подмножество X С Р называется выпуклым, если х < z < у влечет z 6 X для любых х, у G X и любого z € Р. Для X С Р пусть Со(Х) обозначает выпуклую оболочку множества X, то есть наименьшее выпуклое подмножество в Р, содержащее X. Множество Со(Р) всех выпуклых подмножеств в Р, упорядоченное по включению, образует полную решетку, в которой

ДА = Р)Аг, Ai = Co((J Ai)

iei tel iei iei

для произвольных Ai E Со(P), i 6 /.

Для произвольного класса /С частично упорядоченных множеств пусть Со (/С) обозначает класс решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств, принадлежащих классу /С, a S Со (/С) — класс решеток, вложимых в решетки из Со(/С). Далее, пусть V обозначает класс всех частично упорядоченных множеств. Кроме того, для произвольного класса /С С V и произвольного n <uj пусть 1Сп обозначает класс частично упорядоченных множеств из /С, длина которых не превосходит п.

В работе Биркгофа и Беннет [32] была получена характери-зация класса решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств. Позже в работе Семеновой и Верунга [36] было показано, что класс решеток, вложимых в решетки выпуклых подмножеств частично упорядоченных множеств, является конечно базируемым многообразием, а также был найден конкретный базис тождеств этого многообразия. Далее, в работах [37, 38, 39] было получено описание классов решеток (конечных решеток), вложимых в решетки выпуклых подмножеств для различных конкретных классов частично упорядоченных множеств (в частности, для класса частично упорядоченных множеств конечной длины в [37]). Третий основной результат этой диссертации дает описание решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств конечной ограниченной длины.

Теорема 2.1.4 Пусть 0 < п < и. Решетка Ь принадлежит классу Со(Рп) тогда и только тогда, когда она является полной, точечной, непрерывной вверх, а также удовлетворяет условию Алът-вега и тождествам (Нп), (Э).

Таким образом, для любого п < и класс решеток Со(Рп) (класс конечных решеток из СоСРп)) аксиоматизируем на языке первого порядка в классе полных непрерывных вверх решеток (в классе конечных решеток, соответственно), см. следствие 2.1.5.

Частично упорядоченное множество (Р, <) называется лесом, если нижний конус {р £ Р | р < а} линейно упорядочен относительно < для любого а 6 Р. Связный лес называется деревом. Для п > 0 конечное дерево (Р, <) называется п-арным, если каждый элемент а 6 Р имеет не более п верхних покрытий относительно порядка <. Лес называется п-арным, если он является раздельным объединением конечных п-арных деревьев. Пусть Т обозначает класс частично упорядоченных множеств, являющихся лесами, а Т — класс частично упорядоченных множеств, являющихся деревьями. Для любого целого п > 0 пусть Р™ обозначает класс частично упорядоченных множеств, являющихся п-арными лесами, а Тп — класс частично упорядоченных множеств, являющихся

конечными п-арными деревьями.

В работе Семеновой и Замойской-Дженио [40] были описаны решетки, изоморфные решеткам выпуклых подмножеств частично упорядоченных множеств, являющихся лесами. Четвертый основной результат этой диссертации дает характеризацию на языке предикатов первого порядка класса конечных решеток, изоморфных решеткам выпуклых подмножеств п-арных лесов для любого целого п > 0.

Теорема 2.1.12 Для любого целого п > 0 и для любой конечной решетки Ь равносильны следующие условия.

(1) I £ Сорт);

(и) Ь является точечной решеткой и Ь |= (Б), (и), (В), (Тз),

(Т4), Р), (О), (си (Ып).

Отсюда получаем, что класс конечных решеток из Со{Тп) конечно аксиоматизируем в классе всех конечных решеток, см. следствие 2.1.13. Более того, из теоремы 2.1.12 получаем такое

Следствие 2.1.10 Для любого п > 1 имеют место следующие включения:

(1) 8Сорт+1) = 8Со(7~п+1) с 8Сорт+2) = 8Со(Гп+2);

(и) Сорт) С Сорт+1).

Во втором разделе этой главы рассматривается общее понятие идеала в частично упорядоченных множествах. Пусть (Р, <} — частично упорядоченное множество и пусть алгебраический оператор замыкания ¡р определяет пополнение (Р, <). Подмножество I С Р называется (р-идеалом Р, если I = {р 6 Р | Ь(р) £ I'} для некоторого идеала I' решетки замкнутых подмножеств С1(Р, ф).

Через И(Р, ф) мы обозначаем множество всех ^-идеалов в Р. Нетрудно видеть, что И(Р, ср) образует полную решетку по включению. Кроме того, С1(Р, <р) = И(Р, <р), поэтому последняя решетка

является также алгебраической. Частично упорядоченное множество (Р, <) называется (р-дистрибутивным, если решетка Ы(Р, ф) дистрибутивна.

Теорема 2.2.8 Пусть (Р, <) — частично упорядоченное множество и <р определяет пополнение (Р, <), такое что {Р, <) является ц>-дистрибутивным. Если I € М(Р, (р) и Б С Р является направленным вниз множеством, таким что КЛИ ~ 0, то существует простой идеал ф € И(Р, <р), такой что I С и фП!) = 0.

В частности, отсюда следует, что любой идеал в идеально дистрибутивном частично упорядоченном множестве есть пересечение простых идеалов (см. следствие 2.2.10), что обобщает классический результат для решеток и устанавливает ошибочность утверждения из [48, замечание 3.13(1)].

Из леммы Цорна легко следует, что в частично упорядоченном множестве с наименьшим элементом любой простой идеал содержит минимальный простой идеал. Пусть п > 0 и пусть (р определяет пополнение частично упорядоченного множества (Р, <) с наименьшим элементом. Тогда (Р, <} называется п-нормалъным относительно если любой простой идеал из Ы(Р, <р) содержит не более п минимальных простых идеалов. В качестве приложения следствия 2.2.10, мы даем характеризацию п-нормальных нижних полурешеток с наименьшим элементом.

Теорема 2.2.19 Пусть (Р, <) — частично упорядоченное множество с наименьшим элементом и пусть (р определяет пополнение для (Р, <), такое что (Р, <) является (р-дистрибутивным. Рассмотрим следуюище условия для фиксированного п > 0:

0) (Р) <) является п-нормальным относительно <р;

(II) С}о V ... V = Р для любых различных минимальных простых идеалов <5о, ..., <3П € Ы(Р, <р);

(III) 0(<5) является (п + \)-простым (р-идеалом для любого простого идеала <5 6 И(Р, </?);

(iv) Xq V ... V = P для любых xq, ..., xn 6 P, таких что L{xi, Xj) = L(P) для всех i < j ^ n.

Тогда условия (i) и (ii) эквивалентны. Более того, условие (iii) влечет любое из условий (i)-(iv). Если (Р,<) — пиэ/сияя полурешетка с наименьшим элементом, то все четыре условия (i)-(iv) эквивалентны.

Теорема 2.2.19 обобщает аналогичный результат для дистрибутивных решеток с наименьшим элементом, см. Корниш [43, теорема 3.4].

Частично упорядоченное множество (Р, <) с наименьшим элементом называется кусочно п-нормальным относительно <р, если (.L(p),<} с индуцированным порядком < является п-нормальным относительно ц> для любого р е Р. Следующая теорема утверждает, что кусочная нормальность совпадает с нормальностью, и была доказана для дистрибутивных решеток Корнишем [43, теорема 3.6].

Теорема 2.2.21 Пусть {Р, <) является нижней полурешеткой с наименьшим элементом и (р определяет пополнение (Р,<), такое что (Р, <) является <р-дистрибутивным. Следующие условия эквивалентны для любого фиксированного п > 0:

(i) для любого р е Р частично упорядоченное множество (L(p),<) 'c индуцированным порядком < является п-■ нормальным относительно tp;

(ii) (Р, <) является п-нормальным относительно <р;

(iii) для любого I € Id(Р,(р) частично упорядоченное множество (I, <) с индуцированным порядком < является п-нормальным относительно ip.

Список литературы

[1] Allouche J.-P., Baake М., Cassaigne J., Damanik D. Palindrom complexity // Theoret. Comput. Sci. 2003, V. 292, P. 9-31.

[2] Allouche J.-P., Shallit J. Automatic Sequences: Theory, Applications, Generalizations, 2002.

[3] Avgustinovich S. V., Cassaigne J., Frid A.E. Sequences of low arithmetical complexity // Theoret. Informatics Appl., 2006, V. 40, N 4. P. 569-582.

[4] Avgustinovich S. V., Fon-Der-Flaass D. G., Frid, A. E. Arithmetical complexity of infinite words // Words, Languages & Combinatorics III, 2003. P. 51-62, Singapore. World Scientific Publishing. ICWLC 2000, Kyoto, Japan, 2000. March. P. 14-18.

[5] Cassaigne J. Double sequences with complexity mn+1 //J. Autom. Lang. Comb. 1999. V. 4, N 3. P. 153-170.

[6] Cassaigne J., Karhumâki J. Toeplitz words, generalized periodicity and periodically iterated morphisms // European J. Combin. 1997. V. 18. P. 497-510.

[7] Кассень Ж., Петров Ф. В., Фрид А. Э. О возможных скоростях роста языков Тёплица // Сибирский математический журнал. 2011. Т. 52. N. 1. Стр. 81-94.

[8] Choffrut С., Karhumâki J. Combinatorics of words // Handbook of formal languages. 1997. V.l. P.329-438.

[9] Ehrenfeucht A., Rozenberg G. A limit theorem for sets of subwords in deterministic T0L languages // Information Processing Letters. 1973. V. 2-3. P. 70-73.

[10] Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words // Theoretical Computer Science. 2003. V. 299. N.l-3. P. 123-150.

[11] Ferenczi S. Complexity of sequences and dynamical systems 11 Discrete Math. 1999. V. 206. P. 145—154.

[12] Frid A. E. Arithmetical complexity of symmetric DOL words // Theoret. Comput. Sci. 2003. V. 306. P. 535-542.

[13] Frid A.E. Sequences of linear arithmetical complexity // Theoret. Comput. Sci. 2005. V. 339. P. 68-87.

[14] Frid A.E. On possible growths of arithmetical complexity // Theoret. Informaties Appl. 2006. V. 40. N. 3. P. 443-458.

[15] Salimov P. V. Constructing infinite words of intermediate arithmetical complexity // LNCS 5457, Springer Verlag, 2009. P. 696-701.

[16] ■ Ivânyi A. On the d-complexity of words // Ann. Univ. Sci. Budapest. Sect. Comput. 1987. V. 8. P. 69-90.

[17] Quas A., Zamboni L. Periodicity and local complexity // Theoretical Computer Science. 2004. V. 319, Issue 1-3, P. 229-240.

[18] Kamae T., Rao H., Xue Y.-M. Maximal pattern complexity for 2-dimensional words // Theoretical Computer Science. 2002. V. 359. P. 15-27.

[19] Kamae T., Xue Y.-M. Two dimensional word with 2k maximal pattern complexity // Osaka J. Math. 2004. V. 41. P. 257-265.

[20] Kamae T., Zamboni L. Maximal pattern complexity for discrete systems // Ergodic Theory and Dynamical Systems. 2002. V. 22-4. P. 1201-1214

[21] Kamae T., Zamboni L. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory Dynam. System 2002. V. 22. P. 1191-1199.

[22] Koskas M. Complexités de suites de Toeplitz // Discrete Math. 1998. V. 183. P. 161-183.

[23] Lothaire M. Algebraic Combinatorics on Words // Encyclopedia of Mathematics and its Applications. 2002. V. 90.

[24] Morse M., Hedlund G.A. Symbolic Dynamics // American Journal of Mathematics. 1938. V. 60. P. 815—866.

[25] Morse M., Hedlund G. A. Symbolic Dynamics II // American Journal of Mathematics. 1940. V. 62. P. 1—42.

[26] Nakashima I., Tamura J.-I., Yasutomi S.-I. *-Sturmian words and complexity // Journal de Theorie des Nombres de Bordeaux, 2003. V. 15. P. 767-804.

[27] Nivat M. Invited talk at ICALP'97.

[28] Restivo A., Salemi S. Binary patterns in infinite binary words // Formal and Natural Computing, Springer Berlin. 2002. P. 107-118 (Lecture Notion in Comput. Sci. V. 2300).

[29] Биркгоф Г. Теория решеток. Москва, Наука, 1981.

[30] Горбунов В. А. Алгебраическая теория квазимногообразий. Новосибирск: Научная книга, 1999.

English translation: Gorbunov V. A. Algebraic Theory of Quasivarieties. New York NY: Plenum Publishing Corporation, 1998.

[31] Семенова M. В. Вложение решеток в производные решетки // Современные проблемы математики. 2011. V. 15. Р. 67-82.

[32] Birkhoff G., Bennett М. К. The convexity lattice of a poset 11 Order. 1985. V. 2. P. 223-242.

[33] Crawley P., Dilworth R.P. Algebraic Theory of Lattices. Englewood: Prentice-Hall, 1973.

[34] Freese R., Jezek J., Nation J.B. Free Lattices // Mathematical Surveys and Monographs, 42. Providence, RI: Amer. Math. Soc., 1995.

[35] Semenova M. Closure lattices of closure spaces // Contributions to General Algebra. 2008. V. 18. P. 175-188.

[36] Semenova M., Wehrung F. Sublattices of lattices of order-convex sets, I. The main representation theorem //J. Algebra. 2004. V. 277. P. 543-564.

[37] Semenova M., Wehrung F. Sublattices of lattices of order-convex sets, II. Posets of finite length // Internat. J. Algebra Comput. 2003. V. 13. P. 543-564.

[38] Semenova M., Wehrung F. Sublattices of lattices of order-convex sets, III. The case of totally ordered sets // Internat. J. Algebra Comput. 2004. V. 14. P. 357-387.

[39] Semenova M. V., Zamojska-Dzienio A. On lattices embeddable into lattices of order-convex sets. Case of trees // Internat. J. Algebra Comput. 2007. V. 17. P 1667-1712.

[40] Semenova M., Zamojska-Dzienio A. Lattices of order-convex sets of forests // Order. 2010. V. 27. P. 383-404.

[41] Semenova M., Zamojska-Dzienio A. On lattices embeddable into lattices of order-convex sets. II. Star-like posets // Order, online first, DOI 10.1007/sll083-010-9189-6.

[42] Cornish W. H. Normal lattices // J. Auslral. Math. Soc. 1972. V. 14. P. 200-215.

[43] Cornish W. H. n-Normal lattices // Proc. Amer. Math. Soc. 1974. V. 45. P. 48-54.

[44] Gratzer G. General Lattice Theory. Second edition. Birkhauser Verlag, Basel, 1998.

[45] Halas R. Ideals and annihilators in ordered sets // Czech Math. J. 1995. V. 45. P. 127-134.

[46] Halas R., Rachunek J. Polars in ordered sets // Discuss Math. 1995. V. 15. P. 43-59.

[47] Halas R., Joshi V., Kharat V.S. On n-normal posets // Central European Journal of Mathematics. 2010. V. 8. P. 985-991.

[48] Kharat V.S., Mokbel K.A. Semiprime ideals and separation theorems for posets // Order. 2008. V. 25. P. 195-210.

Публикации автора по теме диссертации

[49] Батуева Ц. Ч.-Д. Арифметическое замыкание двумерных слов Тёплица // Дискретн. анализ и исслед. опер. 2009. Т. 16. N 2. С. 3-15.

[50] Батуева Ц. Ч.-Д. Серия двумерных слов с максимальной оконной сложностью 2к I/ Дискретн. анализ и исслед. опер. 2010. Т. 17. N 5. С. 3-14.

[51] Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Вестник НГУ. 2011. N 3. С. 85-94.

[52] Batueva С., Semenova М. Ideals in distributive posets// Central European Journal of Mathematics. 2011. Т. 9. N 6. P. 1380-1388.

[53] Батуева Ц. Ч.-Д. Арифметическое замыкание двумерных слов Тёплица // Материалы XLVI Международной научной студенческой конференции, Новосибирск, 2008. С. 180.

[54] Батуева Ц. Ч. -Д. Серия двумерных слов с максимальной оконной сложностью 2к // Материалы XLVII Международной научной студенческой конференции, Новосибирск, 2009. С. 154.

[55] Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Материалы XLIX Международной научной студенческой конференции, Новосибирск, 2011. С. 26.

[56] Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Материалы IV Международной конференции "Математика, ее приложения и математическое образование" Улан-Удэ, 2011. Ч. 1. С. 260-264.

[57] Batueva Ts. Ideals in distributive posets // International Conference "Mal'tsev Meeting", Collection of Abstracts Novosibirsk, 2011. P. 93.

Подписано в печать 24 октября 2011г. Формат 60x84 1/16. Заказ № 268 Офсетная печать. Объем 1,25 п.л. Тираж 100 экз. Редакдионно-издательский центр НГУ. 630090, г. Новосибирск, ул. Пирогова,2.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Батуева, Цындыма Чимит-Доржиевна

Введение

1 Двумерные элементарные слова Тёплица

1.1 Арифметическое замыкание двумерных элементарных слов Тёплица.

1.1.1 Определения и обозначения.

1.1.2 Связь арифметических подпоследовательностей в неподвижных точках.

1.1.3 Арифметическая сложность при простом т = I.

1.1.4 Арифметическое замыкание для произвольных натуральных чисел т и /.

1.2 Максимальная шаблонная сложностью двумерных элементарных слов Тёплица.

1.2.1 Основные определения.

1.2.2 Вспомогательные утверждения.

1.2.3 Основная теорема

2 Частично упорядоченные множества

2.1 Решетки выпуклых подмножеств.

2.1.1 Основные понятия.

2.1.2 Характеризация класса Со(Уп).

2.1.3 Решетки выпуклых подмножеств п-арных лесов

2.2 Идеалы в частично упорядоченных множествах.

2.2.1 Расширения и идеалы в частично упорядоченных множествах.

2.2.2 Представление простыми идеалами

2.2.3 Идеалы дистрибутивных частично упорядоченных множеств.

2.2.4 Нормальные частично упорядоченные множества

Введение диссертация по математике, на тему "Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств"

Рассмотрим бесконечное одномерное слово v = г;(1)'и(2)г;(3). над конечным алфавитом Е. Подсловом слова у называется слово вида у{г)у{1 + 1). . у (г + п — 1) для некоторых г, п 6 N. Комбинаторная сложность р(п) слова у, введенная Эренфойхтом, Ли и Розенбергом [9] в 1975 году, равна числу подслов слова у длины п. Известно, что одномерное слово непериодично тогда и только тогда, когда его комбинаторная сложность р(п) имеет рост не меньше п + 1, п £ N. Слова с комбинаторной сложностью р(п) = п + 1, то есть непериодичные слова с минимальной комбинаторной сложностью, называются словами Штурма [23, глава 3].

Бесконечным двумерным словом из называется функция N х N Е: ги(2,1) 2,2) ги{2,3) . ги(1,1) гу(1,2) гу(1,3) .

Для двумерных бесконечных слов комбинаторная сложность р(к,1) определяется как количество прямоугольных подслов длины к и высоты I. Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива:

Гипотеза Нива [27] Если функция комбинаторной сложности рш(к, I) двумерного слова ги удовлетворяет условию рги(к,1) ^ Ы для некоторой пары целых чисел {к. Г), то и) имеет по крайней мере один вектор периодичности.

К настоящему времени были доказаны некоторые более слабые формы этой гипотезы, см. [10], [17]. Рассматривались также двумерные аналоги слов Штурма со сложностью, равной Ы 4- 1, см. [5].

Комбинаторная сложность имеет много модификаций. Упомянем такие как ¿-сложность, введенная Иваньи [16] в 1987 году, палиндромная сложность, введенная Аллушем, Бааком, Кассенем и Дамаником [1] в 2002 году, модифицированная сложность Накасимы и других [26], веденная в 2003 году, шаблонная сложность, введенная Рестиво и Салеми [28] в 2002 году.

Арифметическая сложность, введенная Августиновичем, Фрид и Фон-Дер-Флаассом [4] в 2003 году, является модификацией комбинаторной сложности. Арифметической подпоследовательностью слова у называется последовательность у(к)у(к + (1). у{к-\-пв) . с началом в точке к и шагом (¿. Всякое подслово арифметической подпоследовательности слова у называется арифметическим подсловом слова у. Множество всех арифметических подслов слова у называется его арифметическим замыканием. Арифметической сложностью слова у называется функция /(п), равная числу всех его различных арифметических подслов длины п.

Арифметическая сложность для непериодического слова может расти как экспоненциально [12], так и линейно. При этом известна харак-теризация равномерно рекуррентных слов с линейной арифметической сложностью [13]. Кроме того, известны примеры слов, арифметическая сложность которых растет быстрее, чем любой полином, но медленее, чем сп для некоторого с > 1 [15], а также как 9(па), где а — корень некоторого трансцендентного уравнения [7].

Максимальная шаблонная сложность, введенная Камаэ и Замбони [21] в 2002 году, является еще одной модификацией комбинаторной сложности. Как и для обычной комбинаторной сложности одним из направлений изучения сложностей является установление связи между периодичностью слова и значением функции сложности. Наименьшая максимальная шаблонная сложность непереодического слова равна 2к [21, Теорема 1]. Для двумерных слов Камаэ, Рао и Сюэ [18] было доказано, что двумерное слово периодично по двум неколлинеарным направлениям тогда и только тогда, когда оно сильно 2-рекуррентно и его максимальная шаблонная сложность не превосходит 2к — 1 для некоторого к. В работе Камаэ и Сюэ [19] был предложен один пример такого двумерного слова, но полное описание всех слов с максимальной шаблонной сложностью, равной 2к, еще не найдено ни для двумерного, ни для одномерного случаев.

Рассмотрим некоторый выделенный символ о ^ Ей одномерное слово V € (Е и о)"\ Пусть Т°(и) = и и пусть Т1+1{и) получается из Тг(^) последовательной заменой всех вхождений символа о на символы из слова у. Предельная последовательность

Тш{и) = Нт Т\р) оо называется одномерным словом Теплица [6]. Комбинаторная сложность и периодичность таких слов ранее уже исследовались, например, в работах [6] и [22]. Их арифметическая сложность исследовалась в [3] и [4]; кроме того, оказывается, что слова Тёп лица особого вида — это единственные равномерно рекуррентные слова с линейной арифметической сложностью [13].

Под позицией будем понимать пару неотрицательных целых чисел и подразумевать координаты некоторого символа двумерного слова. Пусть натуральные числа т, / ^ 2. Позиция (г,.;) Е № называется з-ключевой, если я — максимальное натуральное число такое, что и Iе делят г и ] соответственно. Позиция называется ключевой, если она является й-ключевой для некоторого 5 > 0.

Построим двумерное бесконечное слово <у.(гп,1) . Сначала заполним нулями все неключевые позиции. Затем все ¿-ключевые позиции для нечетного э заполняются единицами, а все ¿-ключевые позиции для четного й заполняются нулями.

0 о 0 о 0 о 0 о . 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 0

0 о 0 о 0 о 0 о . 0 1 0 0 0 1 0 0

0 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 0

0 о 0 о 0 о 0 о . 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 0

Предельное двумерное слово оцгп,1) называется элементарным словом Теплица.

В данной работе впервые рассматривается арифметическая сложность двумерных слов. Описаны слова арифметического замыкания класса элементарных слов Тёплица. Для некоторых из этих слов посчитана арифметическая сложность. Построена бесконечная двухпарамет-рическая серия двумерных слов, имеющих максимальную шаблонную сложность 2к.

Решетки выпуклых подмножеств частично упорядоченных множеств служат выразительным примером выпуклых геометрий, см. монографию Горбунова [30] и обзорные работы Семеновой [35, 31]. Эти решетки интенсивно изучались рядом авторов, см. работы [32, 36, 37, 38, 39, 40, 41]. В частности, в работе Биркгофа и Беннет [32] была получена характериза-ция класса решеток, изоморфных таким решеткам, откуда следует полудистрибутивность вверх решеток выпуклых подмножеств. В работе Семеновой и Замойской-Дженио [40] были описаны решетки, изоморфные решеткам выпуклых подмножеств частично упорядоченных множеств, являющихся лесами. В работе Семеновой и Верунга [36] было показано, что класс решеток, вложимых в решетки выпуклых подмножеств частично упорядоченных множеств, является конечно базируемым многообразием, а также был найден конкретный базис тождеств этого многообразия. Далее, в работах Семеновой, Верунга и Замойской-Дженио [37, 38, 39, 41] было получено описание классов решеток (конечных решеток), вложимых в решетки выпуклых подмножеств для различных конкретных классов частично упорядоченных множеств (в частности, для класса частично упорядоченных множеств конечной длины в [37]). Очень часто оказывалось, что эти классы решеток являются многообразиями, а для конечных решеток — псевдомногообразиями.

Отметим, что решетки (конечные решетки), вложимые в решетки выпуклых подмножеств деревьев, были описаны в работе Семеновой и Замойской-Дженио [39], где было установлено, что класс таких решеток образует конечно базируемое многообразие (псевдомногообразие, соответственно). Отметим также, что класс решеток, вложимых в решетки выпуклых подмножеств унарных лесов (другими словами, раздельных объединений линейно упорядоченных множеств) был описан в работе Семеновой и Верунга [38], где было показано, что этот класс решеток образует конечно базируемое локально конечное многообразие. В связи с этими результатами естественно возникает вопрос, нельзя ли вложить решетку выпуклых подмножеств произвольного дерева в решетку выпуклых подмножеств п-арного дерева для некоторого п > 0. Один из результатов настоящей работы показывает, что ответ на этот вопрос в общем случае отрицателен. А именно, мы показзываем, что классы решеток, вложимых в решетки выпуклых подмножеств п-арных деревьев и изоморфных таким решеткам, различны для различных п > 0.

В работах Корниша [42, 43] были описаны дистрибутивные решетки с наименьшим элементом, в которых каждый простой идеал содержит не более п минимальных простых идеалов для произвольного фиксированного п > 0. Такие решетки были названы Корнишем п-нормальными. Мы обобщаем это описание на случай частично упорядоченных множеств, которые являются нижними полурешетками с наименьшим элементом.

Приведем краткое описание содержания настоящей диссертации, состоящей из введения, двух глав и списка использованной литературы. Результаты, изложенные в настоящей диссертации, были опубликованы в работах автора [49]-[52] (последняя из них в соавторстве с М. В. Семеновой), см. также тезисы докладов автора на международных конференциях [53]-[57].

Первая глава диссертации посвящена арифметической сложности и максимальной шаблонной сложности двумерных элементарных слов Тёплица.

Неподвижной точкой двумерного морфизма <р называется двумерное бесконечное слово и>, удовлетворяющее равенству <р(ю) = и>. В диссертации исследуются неподвижные ТОЧКИ 0!(т!/) морфизма

О .0 1 о . о о

Р(т,г) : 0 1 о . о о о . о о где т, I ^ 2 и т — ширина, а I — высота образа символа. Слова также являются элементарными словами Тёплица.

Арифметической подпоследовательностью двумерного бесконечного слова ии называется слово ги{х, у)т{х + г, у + ё) . ги{х + пг,у + пд) . с началом в позиции (х,у) и шагом (г, (Г). Арифметической сложностью двумерного бесконечного слова ги называется функция /ш(п), равная числу различных подслов длины п всех его арифметических подпоследовательностей .

Первый основной результат этой диссертации сформулирован в следующей теореме.

Теорема 1.1.19 Пусть т — простое число. Тогда арифметическая сложность двумерного элементарного слова Тёплица а(т}ГП) растет линейно.

Операция инверсии заменяет в слове и символы 1 на 0 и 0 на 1. Полученное слово обозначается через й. Прореживание г>]Ии одномерного слова V = У\У2 ■ • - Уп одномерным конечным словом и получается путем включния слова и между каждыми двумя соседними символами слова V, ТО есть 1>ЦТи = У\ПУ2и . . . иуп.

Введем функцию Т>п(и) = йШ0п-1, где п е №\{0}.

Следующая теорема дает полное описание слов арифметического замыкания двумерного элеметарного слова Тёплица для произвольных значений га и I.

Теорема 1.1.21 Пусть га, I ^ 2. Слово и принадлежит арифметическому замыканию двумерного элементарного слова Теплица а(т,1) тогда и только тогда, когда и или й являются подсловами одного из следующих слов:

1) !2)^(0П) для некоторых ¿,п£ М;

И) Ъгт(у), где V является подсловом слова, полученного способом (1);

111) 2^г(г|); где V является подсловом слова, полученного способом (¿); гу) Т)гр(у), где V является подсловом слова, полученного способом (1), (11) или (ш), р — делитель чисел нок(т, I), т или I соответственно.

В этой главе также рассматривается максимальная шаблонная сложность двумерных элементарных слов Теплица.

Конечное множество т С 1? мощности /с, содержащее пару (0,0), называется к-шаблоном. Функция т —» Е называется т-словом. Некоторое т-слово Ь называется т-подсловом двумерного слова и>, если существует такая пара (х, у), что и>[{х, у)+т] = Ь. Пусть -Рш(т) обозначает множество всех т-подслов слова иМаксимальной шаблонной сложностью слова т называется функция р*и){к)) определенная следующим образом: р1>(к) = та| к 6 М, т — /с-шаблон}.

Двумерное слово называется сильно периодическим, если оно периодично по двум неколлинеарным направлениям (откуда следует периодичность по любому направлению). Известно, что слово сильно периодично тогда и только тогда, когда его максимальная шаблонная сложность строго меньше 2/с для некоторого к (Е М, и слово является строго 2-рекуррентным, см. [18]. Таким образом, 2к — это минимум максимальной шаблонной сложности для строго 2-рекуррентных слов, не являющихся сильно периодическими. До сих пор был известен только один пример таких слов, см. [19].

Второй основной результат этой диссертации, сформулированнный в следующей теореме, предлагает серию таких слов.

Теорема 1.2.5 Для произвольных га, I ^ 2 максимальная шаблонная сложность двумерного элементарного слова Тёплица равна 2к для всех

Для доказательства теоремы 1.2.5 были доказаны две вспомогательные леммы (леммы 1.2.6 и 1.2.7).

Пусть (Р, <) — частично упорядоченное множество. Подмножество ХСР называется выпуклым, если х < г < у влечет 2 Е I для любых х,у £ X и любого Для ХСР пусть Со(Х) обозначает выпуклую оболочку множества X, то есть наименьшее выпуклое подмножество в Р, содержащее X. Множество Со(Р) всех выпуклых подмножеств в Р, упорядоченное по включению, образует полную решетку, в которой

Аг = [)Аг; уАг = Со([]Аг) г€/ г€1 Ш г€/ для произвольных А{ € Со(Р), г Е I.

Для произвольного класса ОС частично упорядоченных множеств пусть Со(ЦС) обозначает класс решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств, принадлежащих классу ОС, а 8Со(Х) — класс решеток, вложимых в решетки из Со(ЗС). Далее, пусть У обозначает класс всех частично упорядоченных множеств. Кроме того, для произвольного класса ОС С У и произвольного п < со пусть 0Сп обозначает класс частично упорядоченных множеств из ОС, длина которых не превосходит п.

В работе Биркгофа и Беннет [32] была получена характеризация класса решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств. Позже в работе Семеновой и Верунга [36] было показано, что класс решеток, вложимых в решетки выпуклых подмножеств частично упорядоченных множеств, является конечно базируемым многообразием, а также был найден конкретный базис тождеств этого многообразия. Далее, в работах [37, 38, 39] было получено описание классов решеток (конечных решеток), вложимых в решетки выпуклых подмножеств для различных конкретных классов частично упорядоченных множеств (в частности, для класса частично упорядоченных множеств конечной длины в [37]). Третий основной результат этой диссертации дает описание решеток, изоморфных решеткам выпуклых подмножеств частично упорядоченных множеств конечной ограниченной длины.

Теорема 2.1.4 Пусть 0 < п < со. Решетка Ь принадлежит классу Со(Уп) тогда и только тогда, когда она является полной, точечной, непрерывной вверх, а также удовлетворяет условию Альтвега и тождествам (Нп); (Э).

Таким образом, для любого п < со класс решеток Со(Уп) (класс конечных решеток из Со(Уп)) аксиоматизируем на языке первого порядка в классе полных непрерывных вверх решеток (в классе конечных решеток, соответственно), см. следствие 2.1.5.

Частично упорядоченное множество (Р, <) называется лесом, если нижний конус {р Е Р | р < а} линейно упорядочен относительно < для любого а £ Р. Связный лес называется деревом. Для п > 0 конечное дерево (Р, <} называется п- арным, если каждый элемент а Е Р имеет не более п верхних покрытий относительно порядка <1. Лес называется п- арным, если он является раздельным объединением конечных п-арных деревьев. Пусть обозначает класс частично упорядоченных множеств, являющихся лесами, а 7 — класс частично упорядоченных множеств, являющихся деревьями. Для любого целого п > 0 пусть обозначает класс частично упорядоченных множеств, являющихся п-арными лесами, аТ™ — класс частично упорядоченных множеств, являющихся конечными гг-арными деревьями.

Теорема 2.1.12 Для любого целого п > 0 и для любой конечной решетки Ь равносильны следующие условия.

I) Ь £ Со(Э*);

II) Ь является точечной решеткой и Ь \= (Б), (и), (В), (Тз), (Т4), (Б), (С), (0П), (Кп).

Отсюда получаем, что класс конечных решеток из Со(Эгп) конечно аксиоматизируем в классе всех конечных решеток, см. следствие 2.1.13. Более того, из теоремы 2.1.12 получаем такое

Следствие 2.1.10 Для любого п > 1 имеют место следующие включения:

1) 8Со(Эг7г+1) = БСо^1) С БСо(?п+2) = ЭСо(Т^2); (п) Со(Эггг) с Со(ЭГ7г+1).

Во втором разделе этой главы рассматривается общее понятие идеала в частично упорядоченных множествах. Пусть (Р, <) — частично упорядоченное множество и пусть алгебраический оператор замыкания ср определяет пополнение (Р, <). Подмножество / С Р называется ф-идеалом Р) если I = {р € Р | Ь(р) Е I'} для некоторого идеала V решетки замкнутых подмножеств С1(Р, ф).

Через Ы(Р, ф) мы обозначаем множество всех ф-идеалов в Р. Нетрудно видеть, что И(Р, ф) образует полную решетку по включению. Кроме того, С1(Р, ф) = И(Р, ф), поэтому последняя решетка является также алгебраической. Частично упорядоченное множество (Р, <) называется ф- дистрибутивным, если решетка И(Р, ф) дистрибутивна.

Теорема 2.2.8 Пусть (Р, <) — частично упорядоченное множество и Ф определяет пополнение (Р, <); такое что (Р,<) является ф-дистрибутивным. Если I € Ы(Р, ф) и И С Р является направленным вниз множеством, таким что I П И = 0, то существует простой идеал М(Р, ф), такой что 1(1С}иС}С\О = 0.

Из леммы Цорна легко следует, что в частично упорядоченном множестве с наименьшим элементом любой простой идеал содержит минимальный простой идеал. Пусть п > 0 и пусть ф определяет пополнение частично упорядоченного множества (Р, <) с наименьшим элементом. Тогда (Р, <) называется п-нормальным относительно ф, если любой простой идеал из 1(1 (Р, ф) содержит не более п минимальных простых идеалов. В качестве приложения следствия 2.2.10, мы даем характери-зацию п-нормальных нижних полу решеток с наименьшим элементом.

Теорема 2.2.19 Пусть (Р, <) — частично упорядоченное множество с наименьшим элементом и пусть ф определяет пополнение для (Р, <}, такое что (Р, <) является ф-дистрибутивным. Рассмотрим следующие условия для фиксированного п > 0:

О {Р, <) является п-нормальным относительно (/?;

11) (¿о V . V = Р для любых различных минимальных простых идеалов . ., С£п £ Ы(Р, <р); ш) 0((5) является (п + 1)-простым (р-идеалом для любого простого идеала £ 1с1(Р, (р); гу) V . V х^ = Р для любых Хо, ., хп £ Р, таких что Ь(хг, х^ = Ь{Р) для всех г < ] ^ п.

Тогда условия (1) и (и) эквивалентны. Более того, условие (ш) влечет любое из условий (1)-(гу). Если (Р, <) — нижняя полурешетка с наименьшим элементом, то все четыре условия (1)-(гу) эквивалентны.

Частично упорядоченное множество (Р, <) с наименьшим элементом называется кусочно п-нормальным относительно если (Ь(р), <) с индуцированным порядком < является п-нормальным относительно (р для любого р Е Р. Следующая теорема утверждает, что кусочная нормальность совпадает с нормальностью, и была доказана для дистрибутивных решеток Корнишем [43, теорема 3.6].

Теорема 2.2.21 Пусть (Р, <) является нижней полурешеткой с наименьшим элементом и </? определяет пополнение (Р, <), такое что (Р, <) является <р-дистрибутивным. Следующие условия эквивалентны для любого фиксированного п > 0:

1) для любого р £ Р частично упорядоченное множество (Ь(р),<) с индуцированным порядком < является п-нормальным относительно <р>; п) (Р, <) является п-нормальным относительно </?;

111) для любого I Е М(Р, ф) частично упорядоченное множество (/, <) с индуцированным порядком < является п-нормальным относительно (р.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Батуева, Цындыма Чимит-Доржиевна, Новосибирск

1. Allouche J.-P., Baake M., Cassaigne J., Damanik D. Palindrom complexity // Theoret. Comput. Sei. 2003, V. 292, P. 9-31.

2. Allouche J.-P., Shallit J. Automatic Sequences: Theory, Applications, Generalizations, 2002.

3. Avgustmovich S. V., Cassaigne J., Frid A. E. Sequences of low arithmetical complexity // Theoret. Informatics Appl., 2006, V. 40, N 4. P. 569-582.

4. Avgustmovich S.V., Fon-Der-Flaass D.G., Frid A. E. Arithmetical complexity of infinite words // Words, Languages k, Combinatorics III, 2003. P. 51-62, Singapore. World Scientific Publishing. ICWLC 2000, Kyoto, Japan, 2000. March. P. 14-18.

5. Cassaigne J. Double sequences with complexity mn + 1 // J. Autom. Lang. Comb. 1999. V. 4, N 3. P. 153-170.

6. Cassaigne J., Karhumäh J. Toeplitz words, generalized periodicity and periodically iterated morphisms // European J. Combin. 1997. V. 18. P. 497-510.

7. Кассенъ Ж., Петров Ф. В., Фрид А. Э. О возможных скоростях роста языков Тёплица // Сибирский математический журнал. 2011. Т. 52. N. 1. Стр. 81-94.

8. Choffrut С., Karhumäh J. Combinatorics of words // Handbook of formal languages. 1997. V.l. P.329-438.

9. Ehrenfeucht A., Rozenberg G. A limit theorem for sets of subwords in deterministic TOL languages // Information Processing Letters. 1973. V. 2-3. P. 70-73.

10. Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words 11 Theoretical Computer Science. 2003. V. 299. N.l-3. P. 123-150.1.l Ferenczi S. Complexity of sequences and dynamical systems // Discrete Math. 1999. V. 206. P. 145-154.

11. Frid A. E. Arithmetical complexity of symmetric DOL words // Theoret. Comput. Sci. 2003. V. 306. P. 535-542.

12. Frid A. E. Sequences of linear arithmetical complexity // Theoret. Comput. Sci. 2005. V. 339. P. 68-87.

13. Frid A.E. On possible growths of arithmetical complexity // Theoret. Informaties Appl. 2006. V. 40. N. 3. P. 443-458.15l Salimov P. V. Constructing infinite words of intermediate arithmetical complexity // LNCS 5457, Springer Verlag, 2009. P. 696-701.

14. Ivanyi A. On the d-complexity of words // Ann. Univ. Sci. Budapest. Sect. Comput. 1987. V. 8. P. 69-90.

15. Quas A., Zamboni L. Periodicity and local complexity // Theoretical Computer Science. 2004. V. 319, Issue 1-3, P. 229-240.

16. Kamae T., Rao H., Xue Y.-M. Maximal pattern complexity for 2-dimen-sional words // Theoretical Computer Science. 2002. V. 359. P. 15-27.

17. Kamae T., Xue Y.-M. Two dimensional word with 2k maximal pattern complexity // Osaka J. Math. 2004. V. 41. P. 257-265.

18. Kamae T., Zamboni L. Maximal pattern complexity for discrete systems // Ergodic Theory and Dynamical Systems. 2002. V. 22-4. P. 1201-1214

19. Катае T., Zamboni L. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory Dynam. System 2002. V. 22. P. 1191-1199.

20. Koskas M. Complexités de suites de Toeplitz // Discrete Math. 1998. V. 183. P. 161-183.

21. Lothaire M. Algebraic Combinatorics on Words // Encyclopedia of Mathematics and its Applications. 2002. V. 90.

22. Morse M., Hedlund G.A. Symbolic Dynamics // American Journal of Mathematics. 1938. V. 60. P. 815-866.

23. Morse M., Hedlund G.A. Symbolic Dynamics II // American Journal of Mathematics. 1940. V. 62. P. 1-42.

24. Nakashima I., Tamura J.-I., Yasutomi S.-I. *-Sturmian words and complexity // Journal de Theôrie des Nombres de Bordeaux, 2003. V. 15. P. 767-804.

25. Nivat M. Invited talk at 1С ALP'97.

26. Restivo A., Salemi S. Binary patterns in infinite binary words // Formal and Natural Computing, Springer Berlin. 2002. P. 107-118 (Lecture Notion in Comput. Sci. V. 2300).

27. Биркгоф Г. Теория решеток. Москва, Наука, 1981.

28. Горбунов В. А. Алгебраическая теория квазимногообразий. Новосибирск: Научная книга, 1999. English translation: Gorbunov V. А. Algebraic Theory of Quasivarieties. New York NY: Plenum Publishing Corporation, 1998.

29. Семенова M. В. Вложение решеток в производные решетки // Современные проблемы математики. 2011. V. 15. Р. 67-82.

30. Birkhoff G., Bennett M. K. The convexity lattice of a poset // Order. 1985. V. 2. P. 223-242.

31. Crawley P., Dilworth R. P. Algebraic Theory of Lattices. Englewood: Prentice-Hall, 1973.

32. Freese R., Jezek J., Nation J. B. Free Lattices // Mathematical Surveys and Monographs, 42. Providence, RI: Amer. Math. Soc., 1995.

33. Semenova M. Closure lattices of closure spaces // Contributions to General Algebra. 2008. V. 18. P. 175-188.

34. Semenova M., Wehrung F, Sublattices of lattices of order-convex sets, I. The main representation theorem //J. Algebra. 2004. V. 277. P. 543-564.

35. Semenova M., Wehrung F. Sublattices of lattices of order-convex sets,1.. Posets of finite length // Internat. J. Algebra Comput. 2003. V. 13. P. 543-564.

36. Semenova M., Wehrung F. Sublattices of lattices of order-convex sets,

37. I. The case of totally ordered sets // Internat. J. Algebra Comput. 2004. V. 14. P. 357-387.

38. Semenova M. V., Zamojska-Dzienio A. On lattices embeddable into lattices of order-convex sets. Case of trees // Internat. J. Algebra Comput. 2007. V. 17. P. 1667-1712.

39. Semenova M., Zamojska-Dzienio A. Lattices of order-convex sets of forests // Order. 2010. V. 27. P. 383-404.

40. Semenova M., Zamojska-Dzienio A. On lattices embeddable into lattices of order-convex sets. II. Star-like posets // Order, online first, DOI 10.1007/sl 1083-010-9189-6.

41. Cornish W. H. Normal lattices //J. Auslral. Math. Soc. 1972. V. 14. P. 200-215.

42. Cornish W.H. n-Normal lattices // Proc. Amer. Math. Soc. 1974. V. 45. P. 48-54.

43. Gratzer G. General Lattice Theory. Second edition. Birkhauser Verlag, Basel, 1998.

44. Halas R. Ideals and annihilators in ordered sets // Czech. Math. J. 1995. V. 45. P. 127-134.

45. Halas R., Rachunek J. Polars in ordered sets // Discuss. Math. 1995. V. 15. P. 43-59.

46. Halas R., Joshi V., Kharat V. S. On n-normal posets // Central European Journal of Mathematics. 2010. V. 8. P. 985-991.

47. Kharat V.S., Mokbel K.A. Semiprime ideals and separation theorems for posets // Order. 2008. V. 25. P. 195-210.Публикации автора по теме диссертации

48. Батуева Ц. Ч.-Д. Арифметическое замыкание двумерных слов Теплица // Дискретн. анализ и исслед. опер. 2009. Т. 16. N 2. С. 3-15.

49. Батуева Ц. Ч.-Д. Серия двумерных слов с максимальной оконной сложностью 2к // Дискретн. анализ и исслед. опер. 2010. Т. 17. N 5. С. 3-14.

50. Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Вестник НГУ. 2011. N 3. С. 85-94.

51. Batueva С., Semenova М. Ideals in distributive posets// Central European Journal of Mathematics. 2011. T. 9. N 6. P. 1380-1388.

52. Батуева Ц. Ч.-Д. Арифметическое замыкание двумерных слов Тёп-лица // Материалы XLVI Международной научной студенческой конференции, Новосибирск, 2008. С. 180.

53. Батуева Ц. Ч.-Д. Серия двумерных слов с максимальной оконной сложностью 2к // Материалы XLVII Международной научной студенческой конференции, Новосибирск, 2009. С. 154.

54. Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Материалы XLIX Международной научной студенческой конференции, Новосибирск, 2011. С. 26.

55. Батуева Ц. Ч.-Д. Решетки выпуклых подмножеств // Материалы IV Международной конференции "Математика, ее приложения и математическое образование", Улан-Удэ, 2011. Ч. 1. С. 260-264.

56. Batueva Ts. Ideals in distributive posets // International Conference "Mal'tsev Meeting", Collection of Abstracts, Novosibirsk, 2011. P. 93.