Содержание к диссертации
Введение
1 Вполне автоматные алгебры 20
1.1 Определения и обозначения 20
1.2 Некоторые вспомогательные утверждения 24
1.3 Распознавание конечной определенности автоматной мономиальной алгебры 37
1.4 Классификация и примеры 37
1.5 Решение некоторых алгоритмических проблем 48
2 Модуль сизигий и базис Гребнера конечно порожденного левого идеала в автоматных мономиальных алгебрах 58
2.1 Вспомогательные утверждения 63
2.2 Конструкция левого модуля сизигий 68
2.3 Конструкция базиса Гребнера левого идеала 69
2.4 Решение некоторых алгоритмических проблем 72
3 Базисы Гребнера в идеалах соотношений алгебр, в которых лиевы элементы образуют конечномерное пространство 76
3.1. Описание процедуры построения базиса Гребнера идеала соотношений, необходимые конструкции 77
3.2 Нахождение линейной невырожденной замены образующих, при которой базис Гребнера определяющего идеала конечный 83
4 Распознавание алгебраической зависимости в конечно порожденных алгебрах 88
4.1 Распознавание алгебраической зависимости элементов автоматной мономиальной алгебры, образующих SAGBI-бъзис порождаемой ими подалгебры 88
4.2 Распознавание алгебраической зависимости конечного числа однородных полиномов одинаковой степени конечно порожденной свободной алгебры 92
- Некоторые вспомогательные утверждения
- Конструкция левого модуля сизигий
- Нахождение линейной невырожденной замены образующих, при которой базис Гребнера определяющего идеала конечный
- Распознавание алгебраической зависимости конечного числа однородных полиномов одинаковой степени конечно порожденной свободной алгебры
Введение к работе
В диссертации изучаются некоторые классы ассоциативных конечно порожденных алгебр и связанные с ними алгоритмические проблемы. Все объекты, свойства и алгоритмические проблемы которых рассматриваются в диссертации, являются автоматными алгебрами над полем нулевой характеристики. Иногда этот факт оговаривается в качестве условия, а иногда — оказывается свойством алгебры, доказательство которого порой весьма нетривиально. Автоматными являются ассоциативные алгебры, множество нормальных слов которых представляет собой регулярный язык. Одно из эквивалентных определений регулярного языка — это множество слов, которые можно прочесть, двигаясь по ребрам конечного ориентированного маркированного графа, отмеченным буквами фиксированного алфавита. Буквы алфавита соответствуют образующим алгебры. Граф, представляющий конечный автомат, называется графом Уфпаровского автоматной алгебры.
Главным отличием регулярных языков, представляющих собой множество нормальных слов некоторой автоматной алгебры, является то, что каждое подслово некоторого слова этого языка снова принадлежит языку. Тем не менее, для работы с автоматными алгебрами зачастую достаточно общего определения регулярного языка, так как регулярные языки обладают достаточным количеством свойств, позволяющих производить практически любые манипулирования с ними. Наиболее стандартные свойства описываются в [5]. Например, замыкание относительно теоретико-множественных операций, распознавание принадлежности языку, равенство двух языков и многие другие. Свойства, носящие более специальный характер, такие как левое и правое, слабое и сильное деления регулярных языков, регулярность языка обструкций некоторого регулярного языка, определяются и доказываются в настоящей
диссертации в первой главе.
Изначально понятие автоматной алгебры вводилось с целью обобщения понятия конечно определенной мономиальной алгебры. Было замечено, что при доказательстве большинства результатов в теории конечно определенных мономиальных алгебр, использовалась, по сути, не финитность множества слов, порождающих идеал определяющих соотношений, а именно регулярность языка ненулевых слов алгебры. Поэтому с развитием теории регулярных языков отпала необходимость рассматривать конечно определенные алгебры как отдельный класс. Отметим, что одной из целей большинства результатов данной диссертации является именно обобщение некоторых известных результатов, использовавших финитность определенных множеств элементов алгебры, на случаи, когда эта финитность может отсутствовать, но удается найти регулярный язык, заменяющий в полной мере эту финитность.
Идеи отказываться от конечности некоторых множеств объектов ради обобщения существующих результатов начали возникать еще давно. Естественным способом заменить эту финитность является задание некоторой эффективной перечисляющей процедуры, которая выдает любое конечное число первых элементов рассматриваемого упорядоченного множества объектов. Одним из примеров таких процедур является конечный автомат, который задает регулярные языки. С развитием теории формальных языков появилось много других способов задания определенных множеств слов, появилась четкая классификация этих способов, называемая классификацией Холмского. Регулярные языки оказались на следующей ступени после конечных множеств в этой классификации. Тем не менее, в большинстве ситуаций обобщать результаты на случаи, скажем, контекстно свободных грамматик не удается, так как этот вид грамматик не обладает ни замкнутостью относительно всех теоретико-множественных операций, ни достаточным набором алгоритмов
распознавания. В частности, алгоритмом распознавания равенства двух языков контекстно свободных грамматик. Поэтому конечный автомат является по сути единственным приемлемым способом задания бесконечного множества слов в теории ассоциативных алгебр.
Еще одним важным достижением в алгоритмических вопросах стало появление стандартных базисов или, в другой терминологии, базисов Гребнера. В диссертации техника стандартных базисов будет использоваться достаточно часто. Первые попытки построения стандартных базисов были сделаны еще в 1926 году. Впервые идеи стандартных базисов в современном их виде возникли в работе А.И.Ширшова в 1962 году, а в 1965 Бухбергером они были определены для полиномиальных идеалов. Им же был рассмотрен первый эффективный алгоритм построения стандартных базисов с помощью критических пар. В 1978 году Бергманом понятие было распространено на свободные ассоциативные алгебры с помощью доказанной им "бриллиантовой леммы". Стандартные базисы в идеалах ассоциативных алгебр называют еще базисами Гребнера. Систематическое изложение фактов, связанных с базисами Гребнера, сделано В.Н.Латышевым в работе [1] в 1988 году и В.А.Уфнаровским в 1990 году.
В подалгебрах ассоциативных алгебр существуют аналоги базисов Гребнера для идеалов — так называемые SAGBI-базисы. Впервые SAGBI-базисы были определены в 1988 году для подалгебр свободной коммутативной алгебры, а в 1999 году Н.К.Иыуду определила это понятие в подалгебрах свободных ассоциативных алгебр. В.Н.Латышев обобщил конструкции базисов Гребнера и SAGBI -базисов до понятия стандартного базиса подполигона линейного полигона, но поскольку для изложения дальнейших результатов диссертации нам необходимы будут только понятия базиса Гребнера и SAGBI -базиса, эта конструкция определяться и использоваться не будет.
Большая часть диссертации посвящена разрешению различных
алгоритмических проблем в автоматных алгебрах. Алгоритмические вопросы в различных классах алгебр исследовались А.И.Ширшовым, В.Н.Латышевым, В.А.Уфнаровским, У.У.Умирбаевым, Т.Гатевой-Ивановой, В.В.Борисепко, А.Я.Беловым, Н.К.Иыуду, Д.И. Пионтковским.
Ряд распознаваемых свойств ассоциативных стандартно конечно определенных алгебр указан В.Н.Латышевым и Т.Гатевой-Ивановой. Н.К.Иыуду положительно решена проблема вхождения в подалгебру свободной ассоциативной алгебры, порожденную конечным числом однородных элементов. У.У.Умирбаевым показано, что для подалгебр свободной ассоциативной алгебры проблема вхождения и проблема распознавания алгебраической независимости конечного множества элементов алгоритмически неразрешимы. С другой стороны, алгоритмически разрешима проблема распознавания алгебраической зависимости мономов. В связи с этим В.Н.Латышевым была поставлена проблема об алгоритмическом распознавании алгебраической зависимости конечного числа однородных полиномов свободной алгебры, не разрешенная до настоящего времени и разрешенная в данной диссертации для случая однородных элементов одинаковой степени. Л.Касапенко в 2000 году был получен результат об алгоритмической разрешимости проблемы распознавания свободной порожденности SAGBI -подалгебр конечно определенных мономиальных алгебр, который обобщается в настоящей диссертации на случай автоматной мономиальной алгебры.
При решении большинства алгоритмических проблем часто возникает необходимость довольно сильно сужать класс алгебр, для которого мы пытаемся разрешить данную алгоритмическую задачу. Для подавляющего большинства таких задач необходимым ограничением является эффективное задание базиса Гребнера у идеала определяющих соотношений рассматриваемой ассоциативной алгебры. Чаще всего ограничиваются заданием порождающих идеала определяющих соотношений алгебры, являющихся элементами
конечного базиса Гребнера этого идеала. В этом случае оказывается разрешимой проблема вхождения элемента в идеал, но для большинства специфических алгоритмических проблем их разрешимость при таком ограничении остается открытой, более того, предполагается их алгоритмическая неразрешимость.
В этой связи "хорошимииявляготся коммутативные ассоциативные алгебры, для которых практически все поставленные алгоритмические проблемы решены. Подробные исследования этих проблем проведены в работах [1, 2]. В данной работе коммутативные алгебры рассматриваться не будут. Известны также еще два класса алгебр, для которых решены некоторые алгоритмические проблемы. Это класс автоматных мономиальных алгебр и класс алгебр с конечной левой и/или правой переработкой. Для таких классов, в частности, решена проблема распознавания делителя нуля. Решение этой и многих других алгоритмических проблем для автоматных мономиальных алгебр и алгебр с конечной переработкой можно найти в работах [3] и [4] соответственно.
Целью первой части диссертации является описание такого класса алгебр, который, с одной стороны, содержит в себе все автоматные мономиальные алгебры и все полугрупповые алгебры с ограниченной переработкой, а с другой — допускает решение некоторых алгоритмических проблем. Для этого вводится понятие вполне автоматных алгебр, которые по способу задания относятся к одному из двух неодинаковых типов.
Также как и в случае определения понятия автоматных мономиальных алгебр, основным инструментом для построения вполне автоматных алгебр являются конечные автоматы (маркированные ориентированные конечные графы) и регулярные выражения Клини. Напомним, -что автоматные мономиальные алгебры можно задать одним из следующих двух эквивалентных способов: регулярным языком ненулевых слов и регулярным языком определяющих мономов.
Во втором случае можно определить либо произвольный регулярный язык, порождающий идеал определяющих соотношений автоматной мономиальной алгебры, либо определить регулярный язык всех нулевых слов.
При рассмотрении полугрупповых алгебр также можно пойти двумя путями, схожими с только что описанными для мономиальных алгебр. Первому такому пути соответствует задание такого регулярного языка над некоторым алфавитом, связанным с алфавитом образующих полугрупповой алгебры, который определенным образом эффективно описывает базис Гребнера идеала определяющих соотношений. Алгебры, построенные таким образом, называются стандартно регулярно определенные (в оригинале би-автоматные) по аналогии со стандартно конечно определенными. Впервые такие алгебры начали изучать шведские математики Нордбек и Мансон в 2002 году в статье [6]. Аналогия с мопомиальным случае заключается в том, что регулярный язык, порождающий мономиальный идеал определяющих соотношений, определяет базис Гребнера этого идеала. Класс стандартно регулярно определенных алгебр значительно расширяет класс стандартно конечно определенных алгебр, но так как содержит его, то не допускает решение тех алгоритмических проблем, которые не были решены в классе алгебр, идеал определяющих соотношений которых обладает конечным базисом Гребнера.
В связи с этим, автор настоящей диссертации пошел в другом направлении, по аналогии с заданием мономиальной алгебры регулярным языком нулевых слов. Задается регулярный язык над некоторым алфавитом, связанным с алфавитом образующих полугрупповой алгебры, который эффективно описывает все мономы или биномы, лежащие в идеале определяющих соотношений. Конечно, все эти биномы и мономы вместе составляют базис Гребнера этого идеала, поэтому такие алгебры, названные вполне автоматными (второго типа), являются стандартно регулярно определенными.
Удается несколько расширить этот класс до класса вполне автоматных алгебр первого типа следующим образом: указанный регулярный язык описывает не все биномы, а только те, которые являются редукциями мономов к их нормальной форме. Ясно, что и такие биномы вместе с мономами образуют базис Гребнера идеала определяющих соотношений.
В диссертации приведена полная исчерпывающая классификация вполне автоматных алгебр, включающая модельные примеры. Решаются некоторые алгоритмические проблемы в классе вполне автоматных алгебр.
Методы работы со специальными регулярными языками, предназначенными для задания вполне автоматных алгебр, могут оказаться весьма полезными в теории формальных языков как самостоятельные результаты. Может представлять интерес дальнейшее изучение указанных регулярных языков.
Теперь сформулируем основные результаты диссертации.
Для нового класса ассоциативных алгебр — вполне автоматных биномиальных алгебр — решены алгоритмические проблемы: распознавание строгой и нестрогой полином и ал ьности (теорема 1.1), распознавание правой и/или левой конечной переработки (теорема 1.2), построение определяющего регулярного языка для алгебры с конечной переработкой (предложение 1.2) и для мономиальных подалгебр свободной ассоциативной алгебры и некоторых вполне автоматных алгебр (теорема 1.3).
Строится левый модуль сизигий конечной системы элементов автоматной мономиальной алгебры Л и базис Гребнера конечно порожденного левого идеала (теоремы 2.1 и 2.2). Решаются алгоритмические проблемы: распознавания существования нетривиального решения линейного уравнения над Л с конечным числом неизвестных — элементов из А (предложение 2.1),
распознавания вхождения элемента в конечно порожденный левый идеал (предложение 2.2), построения семейства порождающих пересечения двух конечно порожденных левых идеалов (предложение 2.3), распознавания того, является ли конечно порожденный левый Л-модуль свободным (предложение 2.4).
Строится эффективный изоморфизм алгебры с конечномерным пространством лиевых элементов на стандартно конечно определенную алгебру (следствие 3.2). В случае, когда размерность этого пространства совпадает с количеством образующих, приводится алгоритм, строящий такую невырожденную линейную замену образующих, что идеал соотношений алгебры, полученной в результате этой замены, обладает конечным базисом Гребнера (следствие 3.1).
Для подалгебр, заданных конечным SAGBI -базисом в автоматной мономиальной алгебре положительно решен вопрос об алгоритмическом распознавании алгебраической зависимости порождающих подалгебры (теорема 4.1). Указан алгоритм распознавания алгебраической зависимости однородных полиномов одинаковой степени в свободной ассоциативной алгебре (следствие 4.1).
Для изложения подробных результатов диссертации введем необходимые обозначения и определения.
Пусть К— поле нулевой характеристики; X = {х\,...,хп} — произвольный алфавит; (X)— свободная полугруппа, порожденная множеством X; К, {X) — алгебра некоммутативных полиномов или свободная ассоциативная алгебра над полем К. с системой образующих (или порождающих) X.
Элементы полугруппы (X) называются некоммутативными мономами или словами, а элементы К (X) — некоммутативными полиномами.
Конечно порожденную ассоциативную алгебру будем называть
полугрупповой (или биномиальной), если ее идеал определяющих соотношений порождается биномами, то есть разностями двух мономов.
Заметим, что произвольная ассоциативная алгебра А = К{Х)/1 изоморфна алгебре некоммутативных полиномов К>{Х) с умножением fog — nov(fg), где nor(/fg относительно идеала Т. Поэтому элементы ассоциативной алгебры мы будем иногда называть полиномами (мономами или словами).
Мы будем использовать степенно-лексикографический порядок на мономах ассоциативной алгебры, если не оговорена другая упорядоченность.
В любом ненулевом полиноме /, нормальном относительно идеала определяющих соотношений, можно выделить старший член /, наибольший среди всех мономов элемента / в данном порядке. Если полином / не является нормальным, то через / обозначим старший член полинома nor(/).
Некоторые множества слов ассоциативной алгебры, порожденной конечным алфавитом X, могут образовывать регулярный язык. Такое множество может быть задано конечным автоматом, который мы всегда будем мыслить как ориентированный маркированный граф, некоторые вершины которого объявлены начальными, а некоторые — конечными. Иногда вершины такого графа мы будем называть состояниями автомата. Обозначим через G множество вершин автомата, а через 2х — множество всех подмножеств конечного алфавита X. Вместо ребер, ведущих из вершины в\ Є 0 к вершине 6 Є и маркированных буквами ж^,... ,Xik, мы часто будем пользоваться понятием функции перехода 5:0x0 —» 2х из состояния 0\ в состояние $2 '
где Xiv...tXik — буквы-маркеры ребер, ведущих из вершины #1 є 0 к вершине #2 Є 0. Таким образом, конечный автомат может быть задан не только ориентированным маркированным графом, но
и пятеркой (X, 0,0О,0О,), где X — конечный алфавит, 0 — множество состояний (вершин) автомата, 0о — множество начальных состояний автомата, 9а — множество конечных состояний автомата, б — функция переходов.
Каждому конечному автомату соответствует некоторое множество слов в алфавите X. Эти слова соответствуют путям в графе из некоторой начальной вершины в некоторую конечную вершину. Слова образуются "приписыванием"справа буквы-маркера текущего ребра.
Множество слов, задаваемое конечным автоматом, принято называть регулярным языком.
Определение 1. Для данного конечного автомата К а , изображаемого ориентированным маркированным графом Гд, и соответствующего ему регулярного языка La рассмотрим множество путей графа Г^, начинающихся в начальных его состояниях, а заканчивающихся в состоянии 9. Через Cf- обозначим множество слов, соответствующих этим путям.
Аналогично определяем put как множество слов, соответствующих путям, начинающимся в в и заканчивающихся в конечных состояниях Ya ) а также Cfg, как множество слов, соответствующих путям, начинающимся в состоянии в, а заканчивающимся в состоянии $'.
Отметим, что jC, jCgJ1* и Cfljg суть регулярные языки. Они задаются автоматами, образованными из Г^ объявлением единственной конечной (для in и io) вершины в и начальной (для out и io) вершины 9' как множества конечных (соответственно начальных) вершин.
Обозначим Cf = /.
Рекурсивно определим понятие регулярного выражения над X:
0 — регулярное выражение
Для любого х Є X х — регулярное выражение
Для любых двух регулярных выражений т\ и 7*2 Г\Г^ и т\ U 7*2 — регулярные выражения.
Для любого регулярного выражения г г* — регулярное выражение.
Каждое регулярное выражение определяет некоторое множество слов в алфавите X. Если регулярные выражения п и 7*2 определяют множества слов R\ и Ri, то регулярные выражения т\Т<і, г\ U 7*2, т* определяют множества слов R1R2, R1UR2 и (Jix)^! соответственно.
Известная теорема Клини утверждает, что любой регулярный язык может быть задан некоторым регулярным выражением, и что любое регулярное выражение определяет некоторый регулярный язык.
Определим понятие обобщенного регулярного выражения, для которого будет справедлив аналог теоремы Клини.
Определение 2. Обобщенным регулярным выражением называется выражение, полученное из регулярных следующим образом. Если п и
7*2 — регулярные ИЛИ Обобщенные регулярные Выражения, TO 7"i U 7*2 ,
Пг2 > ї*і , Гі \ Г2 и г*і П 7*2 также обобщенные регулярные выражения.
Обобщенные регулярные выражения тоже определяют некоторые множества слов в алфавите X. Если обобщенные регулярные выражения 7*1 и 7*2 определяют множества СЛОВ #1 И і?2 ! то обобщенные регулярные выражения Т\\т2 и т*1 П т*2 определяют множества слов R\ \ R^ и R\ П i?2 соответственно. Часто мы будем обозначать множество, определяемое некоторым обобщенным регулярным выражением, тем же символом, что и само обобщенное регулярное выражение.
Известно (см [5]), что дополнение V = X* \ L любого регулярного языка L в алфавите X, является регулярным языком. Поэтому разность и пересечение двух регулярных языков также будут регулярными языками с регулярными выражениями Li\L>2 ~ {L\\JL%f и L\ П Li — (L[ U Ь2)' соответственно.
Тогда имеет место очевидное утверждение.
Предложение 1 (Аналог теоремы Клини). Любой язык, задаваемый конечным автоматом, мооїсет быть задан обобщенным регулярным выражением. Любой язык, задаваемый обобщенным регулярным выражением, люжет быть задан конечным автоматом.
В дальнейшем, вместо термина "обобщенное регулярное выражение"буде использоваться термин "регулярное выражение".
Определение 3. Для любого регулярного языка L в алфавите X языком обструкций языка L называется множество слов 0(L), не имеющих собственных подслое в языке L .
Определение 4. Множество М :r L — {и Є X* \ иЬ П М ф 0} называется слабым правым делением регулярного языка М на регулярный язык L в алфавите X. Аналогично определим слабое левое деление М '.і L — {и Є X* | Lu П М ф 0}, сильное правое деление М ~Т L = {и Є X* \ uL С М] и сильное левое деление M~iL^{ueX*\LuCM}.
Для любого регулярного языка L через К& обозначим некоторый конечный автомат, задающий язык L. Через V(K) будем обозначать множество состояний конечного автомата К.
Для любого монома и ассоциативной алгебры через degu обозначим длину монома и, называемую его степенью.
Определение 5. Назовем ассоциативную алгебру Л — fC{X)/I (полугруппу М) алгеброй (полугруппой) с левой R -переработкой, если существует число R ^ 0, такое, что для всех нормальных мономов p,q Є Л (для всех нормальных слов ptq Є М), q = tfi<72; degqinovfap). Аналогично определяются алгебра и полугруппа с правой Л-переработкой.
Перейдем к подробному изложению работы. Диссертация состоит из 4 глав, 13 параграфов и списка литературы.
В главе 1 определяется класс вполне автоматных биномиальных алгебр, приводится классификация биномиальных и мономиальных алгебр, снабженная модельными примерами. Решаются следующие алгоритмические проблемы: распознавание строгой и нестрогой полиномиальности, распознавание правой и/или левой конечной переработки, построение определяющего регулярного языка для алгебры с конечной переработкой и для мономиальных подалгебр свободной ассоциативной алгебры и некоторых вполне автоматных алгебр.
В 1.1 определяются понятия вполне автоматных биномиальных алгебр первого и второго типов, стандартно регулярно определенных алгебр, свойства строгой и нестрогой полипомиалыюсти и свойства ограниченной степени.
В 1.2 содержатся основные утверждения, позволяющие упростить технику работы с регулярными языками над алфавитом, являющимся произведением двух алфавитов. Основным и наиболее часто используемым далее утверждением является лемма о трех автоматах.
Эти вспомогательные утверждения могут рассматриваться через призму теории формальных языков как самостоятельные результаты и как базовые результаты в изучении регулярных языков над алфавитом, являющимся произведением двух алфавитов.
В 1.3 решается проблема распознавания конечной определенности автоматной мономиальной алгебры.
В 1.4 в виде ориентированного графа приводится классификация полугрупповых и мономиальных алгебр. Для каждого ребра этого графа класс алгебр, соответствующий исходящей вершине ребра, содержит в себе класс алгебр, соответствующий входящей вершине ребра. В этом же параграфе содержатся все утверждения, доказывающие существование каждой стрелки, кроме тех случаев, когда существование стрелки является хорошо известным фактом. Данная классификация является полной: то есть в граф нельзя
добавить ни одной стрелки. Для наглядной демонстрации этого параграф 1.4 снабжен необходимым количеством модельных примеров. Стоит отметить, что вполне автоматные биномиальные алгебры первого и второго типа образуют два несовпадающих класса ассоциативных алгебр.
Здесь же приводится предложение 1.3, определяющее альтернативные способы задания вполне автоматных алгебр обоих типов, и предложение 1.5, показывающее, что в случае выполнения в алгебре условия конечного изменения степени различия между первым и вторым типами нет.
В 1.5 решаются указанные выше алгоритмические проблемы. Заметим, что в утверждениях 1.4 уже содержатся алгоритмы построения некоторых определяющих регулярных языков. Например, в предложении 1.2 указан способ построения определяющего регулярного языка алгебры с конечной переработкой (которая, согласно классификации, является вполне автоматной).
В главе 2 решается проблема построения левого модуля сизигий конечной системы полиномов автоматной мономиальной алгебры и базиса Гребнера левого конечно порожденного идеала автоматной мономиальной алгебры, приводится ряд примеров применения модуля сизигий и базиса Гребнера левого идеала к наиболее распространенным алгоритмическим вопросам в автоматных мономиальных алгебрах. Все необходимые обозначения и конструкции приведены в начале этой главы.
В 2.1 доказываются две основные леммы, необходимые для алгоритмического построения конструкций как левого модуля сизигий, так и базиса Гребнера левого идеала. Первая лемма доказывает финитность представленных процедур, а вторая лемма обеспечивает алгоритмическое описание требуемых конструкций базиса Гребнера и модуля сизигий.
В 2.2 доказывается теорема об описании левого модуля сизигий
конечной системы элементов автоматной мономиальной алгебры, а в 2.3 — теорема об описании базиса Гребнера левого конечно порожденного идеала.
В последнем параграфе 2.4 с помощью приведенных конструкций решаются следующие алгоритмические проблемы: распознавание принадлежности элемента левому конечно порожденному идеалу, вычисление коэффициентов представления этого элемента в виде линейной комбинации порождающих идеала (предложение 2.2); нахождение общего решения линейного уравнения (следствие 2.2); нахождения пересечения двух левых конечно порожденных идеалов (предложение 2.3); распознавание свободного левого конечно порожденного модуля (предложение 2.4).
В главе 3 рассматриваются конечно порожденные ассоциативные алгебры Л = K{X)jI над полем /С нулевой характеристики, удовлетворяющие следующему условию.
Рассмотрим подпространство L линейного К -пространства К.{Х), где подпространство L является свободной алгеброй Ли с порождающими из X. Тогда множество L — {f + I \ f Є L] С А является подпространством линейного /С-пространства А. Рассматриваются алгебры А с условием конечномерности пространства L.
В 3.1 на алгебру А накладываются некоторые условия, при выполнении которых приводится алгоритм, строящий конечное число элементов базиса Гребнера конечно порожденного идеала определяющих соотношений алгебры А, степень которых не превышает заданного числа. Показывается, что алгебра Л автоматная, и описывается регулярный язык нормальных слов автоматной алгебры А.
Эти условия выполняются, в частности, когда L = Span^x + / | х Є X). В 3.2 в этом случае приводится алгоритм нахождения такой невырожденной линейной замены образующий, что идеал соотношений
полученной в результате этой замены алгебры обладает конечным базисом Гребнера.
Здесь же рассматривается общий случай алгебры с конечномерным пространством лиевых элементов и строится изоморфизм этой алгебры на стандартно конечно определенную алгебру (следствие 3.2).
В главе 4 решаются алгоритмические проблемы, связанные с распознаванием алгебраической зависимости элементов определенного вида в некоторых ассоциативных алгебрах. Отметим, что в свободной конечно-порожденной алгебре У. У. Умирбаевым (см. [10]) получено отрицательное решение проблемы распознавания алгебраической зависимости конечного числа элементов, поэтому приходится ограничиваться частными случаями элементов определенного вида.
В 4.1 основным утверждением является теорема 4.1, в которой разрешается проблема алгоритмического распознавания алгебраической зависимости конечного числа элементов автоматной мономиальной алгебры, порождающих SAGBI-подалгебру. Этот результат обобщает результат Л.Касапенко ([11, с. 28-31]) о распознавании этого же свойства в конечно определенной мономиальной алгебре. Предложение 4.2 заимствовано из работы Касапенко, и его доказательство дословно переносится на случай автоматной мономиальной алгебры.
В 4.2 предложение 4.3 является ключом к обоснованию своего следствия 4.1 и определяет алгоритм распознавания алгебраической зависимости конечного числа однородных элементов одинаковой степени свободной ассоциативной алгебры.
Автор выражает глубокую благодарность своему научному руководителю, профессору В. Н. Латышеву, за постановку задач и помощь в работе.
Некоторые вспомогательные утверждения
Доказательство: Регулярность языка обструкций следует из следующего равенства: Действительно, первое вычитание выбрасывает из языка L слова, имеющие собственные подслова в L, не являющиеся суффиксами. Второе вычитание выбрасывает эти суффиксы. П Лемма 1.2. Для произвольных регулярных языков L и М множества М :Г L, М ц L, М -= L, М - i L — суть регулярные языки.
Доказательство: Пусть регулярный язык М задан конечным автоматом К с множеством состояний G. Через обозначим множество тех состояний в Є 0, для которых gut соответственно Cf П L ф 0 , Cfx DL, С D L). Тогда М -г L = (J Cf, М и L = (J С?\
Докажем первое равенство. Включение и Є М :r L означает, что найдутся такие т Є М, І Є L, что т = ul. Но это значит, что найдется некоторое состояние в автомата К, при котором І Є ut н и Є OQ . Остальные три равенства доказываются аналогично. Лемма 1.3. Пусть S — регулярный язык в алдЗавите Хху Тогда ifi(S) \ {0} и ц 2(3) \ {0} суть регулярные языки в алфавитах X и Y соответственно.
Доказательство: Пусть S задается конечным автоматом К — {%ху, 0,0о,ва,). Тогда конечный автомат Ki — (X, 0, 0o,0aj i) задает регулярный язык (pi(S), если х Є Si(9i, 6j) тогда и только тогда, когда найдется у, такой что (х, у) Є 5(6 Bj).
Лемма 1.4. Для произвольных регулярных языков L и М над X существует регулярный язык S(L, М) над X. Доказательство: Пусть автоматы К і и Км задают регулярные языки L и М соответственно. Образуем новые автоматы K L (KfM), заменяя маркирующие буквы хі Є X в графе Кі (Км) на буквы (х{,1) Є X (соответственно (1,%І) Є X). Пусть регулярный язык Si задается автоматом KfL, a 5 - автоматом К м. Тогда, например, можно положить S(L, М)
Необходимо отметить, что для получения дальнейших результатов нам важны не только сами регулярные языки 5 над Хх,у но также и множества ф(3). Поэтому помимо замкнутости класса регулярных языков относительно основных теоретико-множественных операций нам хотелось бы иметь аналогичный результат в классе множеств пар слов (5) для регулярных языков S над Хх,у Этот результат обеспечивается следующей леммой.
Пусть Si и S% — регулярные языки над Хху Тогда существуют такие регулярные языки 5з, 54 и S? над Хх,у, что
Доказательство: Положим X = X U {0}, У — Y U {0} Ясно, что регулярный язык 5з = Si U 52 удовлетворяет условию а). Кроме того имеют место равенства Из них вытекает, что нам достаточно доказать для любого регулярного языка 5 над Хх,у существование такого регулярного языка Т над Хх,у, что 0(Г) = (X ) х (У) \ 0(5).
По лемме 1.3 множества /?i(S) и 2(5) суть регулярные языки над Xі И У соответственно. Положим Li = (Xf) \ipi(S), і = 1,2. Тогда Li и І/2 также являются регулярными языками над X и У соответственно. По лемме 1.4 множество — регулярный язык над Хх,у Если пара (u,v) принадлежит 0(5), то u Li и v Li, откуда (и, v) не принадлежит множеству ф(Т). Если же пара (%v) не лежит в 0(5), тогда либо u Lj и (u,v) є S(Lu ( ) ), либо г» Є L2 и (г , и) Є 5((Х ) ,г). В любом случае (u, v) Є 0(Т). Поэтому ф(Т) = (X ) X (У) \ 0(5). П
Лемма 1.6 (Лемма о трех автоматах). Пусть регулярные языки в алфавитах соответственно. Тогда существует регулярный язык 5 б алфавите Ххк+1,х1} задающий множество
Доказательство: Пусть регулярные языки Si задаются соответственно автоматами Образуем из них новые автоматы К{ над теми же алфавитами, добавив для каждого 6ц в переход (1,1) Є 6і(6у,ву). Через SI обозначим регулярные языки, задаваемые автоматами К( соответственно. Ясно, что 5 Э Si и 0(50 = 0(5,).
Конструкция левого модуля сизигий
Предложение 1.4. Пусть S — регулярный язык в алфавите X и S задан автоматом К. Тогда следующие два условия эквивалентны: 1. Существует такое постоянное число d, что для као/сдого слова w языка S выполняется неравенство deg( i(w)) — deg(v 2(«0) d, 2. Все циклы автомата К однородны.
Доказательство: 1)= 2). От противного. Пусть uwv Є S, w Є Cft9{K) и deg( pi(w)) - deg((f2(w)) = a 0. Пусть deg(y i(uu)) -deg(jip2(uv)) — 6. Тогда для любого натурального М найдется такое натуральное к, что deg((pi(uwkv)) — deg((p2(uwkv)) = каЛ-b М. В частности ka + b d. Противоречие.
1). Рассмотрим все слова из S, соответствующие маршрутам в графе К, не проходящим дважды через одну и ту же вершину. Таких слов конечное число, так как автомат К конечен. Для таких слов требуемое d существует и легко находится. Оно же будет искомым требуемым для всех слов автомата К, поскольку все его циклы однородны.
Следствие 1.1. Пусть А вполне автоматная биномиальная алгебра и ее идеал определяющих соотношений задается регулярным языком S нерасщепляющихся редукций и — norii. Тогда А удовлетворяет условию конечного d-изменения степени в том и только том случае, когда произвольный конечный автомат, задающий язык S, содержит только однородные циклы.
Доказательство: Действительно, возьмем два нормальных слова и, v. Тогда представление редукции uv — пог(ш ) через нерасщепляющиеся редукции будет иметь вид uv — nor(uv) = WQ{U\ — nor(ui))wi, где щ — nor («і) — некоторая нерасщеп л я ющаяся редукция. Но тогда deguti — deg(noruw) = degui —deg(nor i) = deg( i(it;)) — deg C )) d для некоторого w Є 5, что вместе с предложением 1.4 доказывает следствие. D
Лемма 1.14. Пусть S — регулярный язык в алфавите X и существует такое постоянное число d, что для каждого слова w языка S выполняется неравенство deg( i(w)) — deg( p2(w)) d. Пусть конечный автомат К построен по некоторому обобщенному регулярному выражению, задающему язык S. Тогда существует такое постоянное число D, что для каоюдого состояния 0 автомата К и для каоюдого слова w языка С1{К) выполняется неравенство deg( pi(w)) deg( 2(w)) D.
Доказательство: Представим S в виде S = S1 U S" U Sf", где S — регулярный язык в алфавите A", p2{Stf) = 0 и tpi(S" ) = 0. Для регулярных языков S" и S" утверждение леммы очевидно. Пусть им соответствуют целые числа D" и D ".
Пусть S задается обобщенным регулярным выражением 5" = S\ U ... U 5t звездной высоты а, где Si — w S wn ... S k.wiki, a Sij — регулярные выражения звездной высоты не выше а — 1. Языки Зц однородны согласно предложению 1.4.
Докажем лемму индукцией по а. Если и — 0, то Si = щ = Wio - Щк{ и S — конечный язык, для которого лемма, очевидно, следует из ограниченности степени всех слов из S. Пусть Do соответствует этому конечному языку.
Пусть теперь Dij — числа, соответствующие по предположению индукции регулярным выражениям 5у. Рассмотрим произвольное состояние в автомата К, построенного по S . Тогда если состояние в не принадлежит ни одному циклу Sij или находится в вершине такого цикла, то в силу однородности языков Sij для любого слова w из Cf выполняется неравенство deg( /?i(w)) — deg( p2(w)) А)-Если же состояние В принадлежит циклу Sij, то существует состояние в , являющееся вершиной этого цикла. Пусть слово w Є С, тогда w можно записать в виде w — uv, где и Є JCJJ? , a v є f, в, причем будем считать v минимальным. Пусть автомат Кц построен по обобщенному регулярному выражению Sij. Тогда Кц изоморфен пучку циклов автомата К с вершиной в . Поэтому справедливо включение v Є $;(Kij), где состояние в" графа Кц соответствует состоянию в пучка цикла автомата К с вершиной в в .
По доказанному deg( (и)) — deg(ip2 (и)) \ DQ. Но по предположению индукции deg(y?i(u)) — deg(v?2(w)) Dij. Поэтому deg(v?i(w)) - deg(vJ2(w)) = deg(v?i(«w)) - deg(v?2(«u)) o + Aj A) + maxy D . Поэтому D max(I ", ? ", DQ + max Aj) удовлетворяет условию леммы. D Лемма 1.15. Пусть S — регулярный язык в алфавите X и существует такое постоянное число d, что для каждого слова w языка S выполняется неравенство deg( i(to)) — deg( 2()) d. Тогда существует регулярный язык S такой, что ф{3 ) = {{u,v) Є tp{S) и degiex t } будет регулярным языком, который мооюет быть построен из языка S.
Нахождение линейной невырожденной замены образующих, при которой базис Гребнера определяющего идеала конечный
Следующая лемма принадлежит Галлиго, Байеру и Стилману. Более подробно с результатами, изложенными в леммах 3.1 и 3.2, можно познакомиться в [9].
Лемма 3.1. Пусть /С — бесконечное поле, и I К\Х] — однородный идеал (то есть идеал, порожденный однородными полипомами). Тогда существует такая линейная невырожденная замена / образующих Xi,..., хп, что в новых переменных идеал старших (/(/)) будет инвариантным относительно любого преобразования образующих с помощью невырожденной верхнетреугольной матрицы. Замечание. Пусть, как и в лемме 3.1, / = (fi,..-,fm) 1С[Х]. Рассмотрим линейную замену переменных ж,- в общем виде: где элементы матрицы Н = (h?) будем считать независимыми переменными. При такой невырожденной замене / превратится в идеал Н(1) = (Я(/і),.,., H(fm)) = (1,..., qB) с базисом Гребнера qi,...,ga.
Коэффициенты при мономах у элементов Н(/,) суть многочлены от переменных h\ , которые можно выписать в явном виде. При помощи алгоритма Бюхбергера нахождения базиса Гребнера идеала находятся коэффициенты при старших мономах элементов qi,...,q3. Они также будут являться полиномами от h\ над К.
В лемме Галл и го-Байер а-Сти л мана показывается, что невырожденная линейная замена Н переменных хі будет искомой при всех таких наборах переменных h\, что коэффициенты при старших мономах элементов qi,...,qs окажутся ненулевыми. Поэтому для фактического построения нужной замены достаточно найти значения переменных k\ , не удовлетворяющих построенной конечной системе уравнений (то сеть конечной системе равенств нулю старших коэффициентов qi,...,qs).
Необходимо также отметить, что в случае, когда I порожден мономами, старшие коэффициенты элементов базиса Гребнера идеала Н{1) будут являться также полиномами от Щ, но уже над Z. Мы можем заполнить в произвольном порядке матрицу размера п У. п фиксированным набором из п2 алгебраически независимых над Z чисел, и получить тем самым универсальную замену для произвольного мономнального идеала /. Известен также еще один результат. Верно и обратное утверждение.
Мы можем произвести такую замену образующих х\,..., хп, чтобы идеал H(J) был инвариантен относительно верхнетреугольной замены образующих. Это можно сделать в силу лемме 3.1. Тогда и подавно он будет инвариантен относительно гомотетии образующих, а значит и мономиален по лемме 3.2.
Пусть один из порождающих мономов идеала Н( J) К\Х]. Произведем замену Xj — ХХІ + Xj. При этой замене w — (Xxf + xAw1 = V [ ] As— = w, 1 f=JW j поскольку H(J) инвариантен относительно такой замены. Отсюда можно заключить, что w — х ... Х(г H{J) влечет за собой V/ iT ff Є H(J), откуда Vn{J) И = {1}.
Теорема 3.5 (О поднятии базиса Гребнера). Существует такая линейная невырожденная замена образующих алгебры А, что базис Гребнера идеала определяющих соотношений I образовавшейся алгебры А конечен и состоит из всех элементов tpq и из элементов д\,... ,д3} описанных выше. Такая замена может быть найдена алгоритмически.
Доказательство: Выше было показано, что алгоритмически может быть найдена такая линейная невырожденная замена Н образующих алгебры А, при которой Vfj(jAw) — {1}.
Но тогда множество Т коммутативных мономов от X равно Т = То U {vi,... ,v8}, где Vi — все минимальные порождающие мономиального коммутативного идеала J. Так как То со, то множество Т конечно. По теореме 3.1, это множество порождает идеал старший частей определяющего идеала / алгебры А. Из конечности Т следует конечность базиса Гребнера идеала /, поскольку множество {vi,..., va} совпадает со множеством {дъ ..., gs}, то базисом Гребнера идеала I является множество где, как и прежде, tpq — хр хч - \ \{/{.
В заключение стоит отметить, что всякая алгебра А с условием конечномерности пространства лиевых элементов изоморфна некоторой алгебре fC{Y)/X с условием dimL — \Y\, Действительно, имеет место простая лемма. Лемма 3.3. Для произвольных / Є K,{X)j I выполнено K{X)JI = /с(х,у)/((й-д) + /) Доказательство: Возьмем гомоморфизм р : K,{X,Y) — fC{X)/I такой, что р в слове от X, Y заменяет каждый у І на / . П Из леммы 3.3 следует, что A = К{Х, Y)/X, где Z = / + (у{ — fi) и X содержит все элементы Xi Xj 2 HkXk - 2 bjkVk, У і Xj - 2 Kjkxk 2 &зкУЬі k k k k vt yj-Ys xbkXk - 2 thy - (3-4) k k Из того, что алгебра А — fC(X)/I удовлетворяет условию конечномерности пространства лиевых элементов, состоящего из \Х\ элементов х\ + /,..., хп -J- /, из теоремы 3.5 и леммы 3.3 вытекают следствия.
Следствие 3.1. Пусть для конечно определенной ассоциативной алгебры А — К{х\,... ,хп)/1 подпространство L С А представляет собой пространство лиевых элементов алгебры А и L = Span a + /,..., хп + I), тогда существует такая невырожденная линейная замена образующих Xi, что идеал соотношений образовавшейся алгебры имеет конечный базис Гребпера, эффективно строящийся по определяющим соотношениям идеала I.
Распознавание алгебраической зависимости конечного числа однородных полиномов одинаковой степени конечно порожденной свободной алгебры
Поскольку Л — автоматная мономиальная алгебра, то А = C{X)/(L), где L — некоторый регулярный язык. Пусть язык L задан некоторым конечным детерминированным автоматом К, множество состояний которого есть 0 = {$i,..., 9Р}, а переход между состояниями осуществляется по буквам алфавита X.
Обозначим через д{ нормальный относительно (L) старший моном элемента fi, т.е. д = / . Тогда, согласно предложению 4.2, для того, чтобы проверить, является ли подалгебра В свободной со свободными порождающими /i, ...,/т достаточно проверить, является ли множество G = {pi,..-,pm} кодом (предложение 4.1 позволяет это сделать), а также проверить, существуют ли д ,..., git Є G, такие, что д .. .дц Є (L). Приведем алгоритм, который это делает.
Шаг 1. Образуем множество С G, такое, что ді Є Н\ тогда и только тогда, когда ді представляется в виде произведения zw, где z Є X , w Є С для некоторого состояния в. Рассмотрим также все состояния в, для которых найдутся слово z и некоторое gi, такое, что gi = zw, w Є С. Они образуют множество Gi.
Шаг t. Пусть после предыдущего шага мы имеем множества Ht \ и Ot-i, тогда образуем множество, такое, что д ... git Є Ht в следующих случаях и только в них:
Элемент а произведение представляется в виде zw, где гЄГ,шє С для некоторого состояния в Рассмотрим все не лежащие в IJ i j состояния в, для которых найдутся слово z и произведение Qt
Предложение 4.3. Если мнооїсество {д#} является кодом, то алгебраическая зависимость элементов из F эквивалентна их линейной зависимости.
Доказательство. Линейная зависимость, очевидно, является алгебраической. Пусть есть алгебраическое соотношение между полиномами из F, где Р{уи..., ут) є /С{уі,..., ут). Будем считать, что полином минимальный по степени из всех таких полиномов. Представим полином Р в виде суммы мономов, затем вынесем за скобки одинаковые yjtl (в силу условия, что {(} — код, gij ф А, а значит, можно считать свободный член Р нулевым), а то, что останется в скобках, обозначим через F{:
Тогда исходное соотношение Р(/і,..., /m) = 0 можно представить в виде где каждый элемент Fi(fi,...,fm) не равен нулю, так как иначе мы имели бы соотношение Fi(fi,...,frn) = 0, такое, что степень Fi{yu - - -1 Ут) Ф 0 меньше степени Р(г/і,..., г/т). А это противоречит выбору Р. Для любого конечного числа полиномов всегда можно алгоритмически распознать их линейную зависимость. Поскольку слова одинаковой длины всегда образуют код, верно
Следствие 4.1. Существует алгоритм проверки алгебраической зависимости конечного числа однородных полипомов одинаковой степени конечно-порожденной свободной алгебры.
Доказанное следствие обобщает теорему Сардинаса-Петерсона на случай однородных полиномов одинаковой степени. Как уже отмечалось, в общем случае задача распознавания алгебраической зависимости конечного числа элементов свободной алгебры алгоритмически неразрешима (см. [10]). Эта проблема остается открытой в предположении конечного числа произвольных однородных полиномов.
