Распознавание некоторых свойств автоматных алгебр

• Автор: Илясов, Станислав Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 96 с.

1 Вполне автоматные алгебры

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

1.2 Некоторые вспомогательные утверждения

1.3 Распознавание конечной определенности автоматной

мономиальной алгебры

1.4 Классификация и примеры

1.5 Решение некоторых алгоритмических проблем

2 Модуль сизигий и базис Гребнера конечно порожденного левого идеала в автоматных мономиальных алгебрах

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

2.2 Конструкция левого модуля сизигий

2.3 Конструкция базиса Гребнера левого идеала

2.4 Решение некоторых алгоритмических проблем
3 Базисы Гребнера в идеалах соотношений алгебр, в которых лиевы элементы образуют конечномерное пространство
3.1 Описание процедуры построения базиса Гребнера идеала
соотношений, необходимые конструкции
3.2 Нахождение линейной невырожденной замены образующих,
при которой базис Гребнера определяющего идеала конечный

4 Распознавание алгебраической зависимости в конечно порожденных алгебрах
4.1 Распознавание алгебраической зависимости элементов автоматной мономиальной алгебры, образующих £ЛС1?/-базис порождаемой ими подалгебры
4.2 Распознавание алгебраической зависимости конечного числа однородных полиномов одинаковой степени конечно порожденной свободной алгебры

В диссертации изучаются некоторые классы ассоциативных конечно порожденных алгебр и связанные с ними алгоритмические проблемы. Все объекты, свойства и алгоритмические проблемы которых рассматриваются в диссертации, являются автоматными алгебрами над полем нулевой характеристики. Иногда этот факт оговаривается в качестве условия, а иногда — оказывается свойством алгебры, доказательство которого порой весьма нетривиально. Автоматными являются ассоциативные алгебры, множество нормальных слов которых представляет собой регулярный язык. Одно из эквивалентных определений регулярного языка — это множество слов, которые можно прочесть, двигаясь по ребрам конечного ориентированного маркированного графа, отмеченным буквами фиксированного алфавита. Буквы алфавита соответствуют образующим алгебры. Граф, представляющий конечный автомат, называется графом Уфнаровского автоматной алгебры.
Главным отличием регулярных языков, представляющих собой множество нормальных слов некоторой автоматной алгебры, является то, что каждое подслово некоторого слова этого языка снова принадлежит языку. Тем не менее, для работы с автоматными алгебрами зачастую достаточно общего определения регулярного языка, так как регулярные языки обладают достаточным количеством свойств, позволяющих производить практически любые манипулирования с ними. Наиболее стандартные свойства описываются в [5]. Например, замыкание относительно теоретико-множественных операций, распознавание принадлежности языку, равенство двух языков и многие другие. Свойства, носящие более специальный характер, такие как левое и правое, слабое и сильное деления регулярных языков, регулярность языка обструкций некоторого регулярного языка, определяются и доказываются в настоящей

deg щ = deg Vi для всех і, и даже d = 1. Рассмотрим конкретный язык Si.
Вновь воспользуемся индукцией по а и ki. Если слова уо = 7і(гдо) иго = (р2(Що) не содержаться одно в другом, то их лексикографическое сравнение и дает соответствующий ответ на поставленный в лемме вопрос для языка Si. Поэтому будем считать, что гдо = w'w", где V’(itf') = (zq,zq) , фіги") = (у', 1) и deg у' — с.
Положим рекурсивно со = degyo — deg20 = с, Cj — Cj_i + deg yj — degZj, где yj — минимальный из тех индексов г > 0, для которых deg д ^ Cj_i. Пусть тогда zko = z'z", где deg z' = cfco_!.
Для всех 1 ^ fc ^ fc0 положим Xе*-1 = {гд-^ | 1 < г ^ nCfe~1}, где п = |Х]. Пусть ukv^ такие слова в алфавите X, что ф(и^к>) — 1) и ф(и^) = (1 ,wk^). Рассмотрим для всех p,q,k, 1 ^ к ^ fco регулярные ЯЗЫКИ Тр^ = Up^SikV. Наконец, ПОЛОЖИМ Wp0 ~ у' и = z'.

Для регулярных языков Tpq по предположению индукции строится
(к)
алгоритм определения существования такого слова s G Tpq', что degjegiex 94(s) < degdeg]ex , a также алгоритм определения
существования такого слова s Є Tpq , что degdeg]ex tp (s) Д
degdegiex Рассмотрим последовательность
T’t1) 7ЧІ) 7Ч1) 7^(1) чЧ2) 7(2) гр( 2)
PoPl’ PlP2> ■lP2P3’ • • • ’ Pl^lPli’ P1P2’ P2P3> ■ • • > ■lPi2-iPi2’
7(3) 7ЧМ)) /1
P1P2’
(1) (2) (fco-1) (fco)
с краевыми условиями гд^'уі = ..., уко-і - zko-iWyp,', а
также с тем условием, что либо
1) для некоторого языка ТркРШ существует такое слово s, что
degdegiex (s) < degdeglex ^2(5), а во всех предшествующих языках найдутся симметричные слова, либо
2) во всех языках последовательности найдутся симметричные слова.