Распознавание некоторых свойств автоматных алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 512.554.5

Илясов Станислав Александрович

РАСПОЗНАВАНИЕ НЕКОТОРЫХ СВОЙСТВ АВТОМАТНЫХ

АЛГЕБР

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат

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

Москва 2006

Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: Официальные оппоненты:

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

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

профессор В. Н. Латышев

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

доцент В. Л. Куракин,

кандидат физико-математических наук,

с.н.с В. В. Борисенко

Тульский государственный

педагогический университет

им Л. Н. Толстого.

Защита диссертации состоится 7 апреля 2006 г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 7 марта 2006 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В. Н. Чубариков

Jl¿Q&6A

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Регулярными языками математики активно занимались в прошлом веке, и сейчас теория формальных языков и грамматик предоставляет богатый выбор инструментов работы с бесконечными рекурсивно заданными множествами, но наиболее широкое применение в алгоритмических вопросах для ассоциативных алгебр приобрела именно теория регулярных языков. Семейство регулярных языков не только замкнуто относительно стандартных теоретико-множественных операций, но и в настоящее время обладает огромным числом различных алгоритмов распознавания- начиная с распознавания включения в регулярный язык, конечности регулярного языка и равенства двух регулярных языков и заканчивая недавно полученным алгоритмом распознавания звездной высоты регулярного языка и отыскания соответствующего минимального регулярного выражения. Исследование вопросов, связанных с регулярными языками, можно найти в работе А.Саломаа1. В теории ассоциативных алгебр регулярные языки получили широкое распространение и используются для задания автоматных алгебр. Автоматные мономиальные алгебры изучались В.Н.Латышевым, В.В.Борисенко и А.Я.Беловым2, В. А. Уфнаровским и другими математиками.

Впервые идеи стандартных базисов в современном их виде возникли в работе А.И.Ширшова (1962)3, а в 1965 Бухбергером4 они были определены для полиномиальных идеалов. Бергман (1978)5 распространил это понятие на свободные ассоциативные алгебры. Систематическое изложение фактов, связанных со стандартными базисами, сделано В.Н.Латышевым (1988)6. В последнее время появился целый ряд статей, посвященных обобщениям и применению стандартных базисов,

"Саломаа А., Жемчужины теории формальных языков // Мир, 1986.

3Белов А. Я.. Борисенко В. В., Латышев В Н , Мономиальные алгебры // Итоги науки и техники, сер. Современная математика и ее приложения, Тематические обзоры, т. 26, с. 35-214, Москва, 2002.

3Ширшов А. И. Некоторые алгоритмически: проблемы для ají¿e6p Ли // Сиб мат жур. - 1962, 3, N 2, с. 292-296

4Buchberger В. An algorithm for finding a basts for the residue class ring of a zero dimensional polynomial tdeal // Ph.D thesis — 1965. — Univ. of Innsbruck, Math. Inst

'Bergman G. The diamond lemma for ring theory // Adv. math. — 1978. — 29, N 2, p. 178-218

•Латышев В. H.t Комбинаторная теория колец. Стандартные базисы. // МГУ, 1988,

68с.

что подтверждает интерес к изучения стандартных базисов. Н.К.Иыуду (1999)7 изучала стандартные базисы в подалгебрах (SAG ВТ -базисов) свободных ассоциативных алгебр. В.Н.Латышев обобщил понятие стандартного базиса, что позволило строить стандартный базис в подполи-гонах линейных полигонов.

Что касается вопросов о существовании различных алгоритмов распознавания, то ряд распознаваемых свойств ассоциативных стандартно конечно определенных алгебр получен В.Н.Латышевым и Т.Гатевой-Ивановой (1988)8.

Некоторые алгоритмические проблемы в алгебрах с ограниченной переработкой рассматривались Д.И.Пионтковским .

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

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

Научная новизна. Результаты диссертации являются новыми. Основными из них являются следующие:

1) Рассматривается новый алгебраический объект — вполне автоматные биномиальные алгебры, обобщающий некоторые существующие классы алгебр. Приводится классификация полугрупповых алгебр с учетом вполне автоматных алгебр, приводятся соответствующие примеры. Решается ряд стандартных алгоритмических проблем для вполне автоматных биномиальных алгебр: распознавание строгой и нестрогой полиномиальности, распознавание правой и/или левой конечной переработки, построение определяющего регулярного языка для алгебры с конечной переработкой и для мономиальных подалгебр свободной ассоциативной алгебры и некоторых вполне автоматных алгебр.

2) Строится левый модуль сизигий конечной системы элементов ав-

7 Иыуду Н К . Стандартный базис и проблема вхождения в подалгебры свободной ассоциативной алгебры // Межд алг сем., поев. 70-летию каф. высш. алг., Москва, 1999.: Тез. докл — Москва, 1999, с 29-31

•Gateva-Ivanova Т , Latyshev V N On the recognizable properties of associative algebras // Special vol of J S С On сотр. aspects comm. algebras London. Acad Press. — 1988 — p 237-254

'Д. И. Пионтковский, Некоммутативные базисы Грёбнера, когерентность ассоциативных алгебр и делимость в полугруппах // Фундаментальная и прикладная математика, т. 7, н. 2, с. 495-513, Москва, 2001.

томатной мономиальной алгебры А и базис Гребнера конечно порожденного левого идеала. Решаются алгоритмические проблемы, связанные с модулем сизигий и базисом Гребнера левого идеала: распознавания существования нетривиального решения линейного уравнения над А с конечным числом неизвестных — элементов из А, распознавания вхождения элемента в конечно порожденный левый идеал, построения семейства порождающих пересечения двух конечно порожденных левых идеалов, распознавания того, является ли конечно порожденный левый Л-модуль свободным.

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

4) Для подалгебр, заданных конечным SAGBI -базисом в автоматной мономиальной алгебре положительно решен вопрос об алгоритмическом распознавании алгебраической зависимости порождающих подалгебры. Указан алгоритм распознавания алгебраической независимости однородных полиномов одинаковой степени в свободной ассоциативной алгебре.

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

Апробация работы. Результаты диссертации докладывались и обсуждались на семинаре "Кольца и модули "в 2004-2005 годах и на научно-исследовательском семинаре кафедры высшей алгебры механико-математического факультета МГУ в 2005 году.

Публикации. Основные результаты диссертации опубликованы в работах автора [1-4], перечисленных в конце настоящего автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, тринадцати параграфов и списка литературы из 15 наименований работ. Общий объем — 96 страниц.

Краткое содержание работы

Везде рассматриваются ассоциативные алгебры над нолем нулевой характеристики.

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

В первой главе определяется класс вполне автоматных биномиальных алгебр, приводится классификация биномиальных алгебр, снабженная модельными примерами. Шведские математики П.Нордбек и Й.Мансен (2002)10 впервые рассмотрели регулярные языки над алфавитом, являющимся декартовым квадратом конечного языка, и способ задания базиса Гребнера идеалов соотношений некоторых полугрупповых алгебр с помощью таких регулярных языков.

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

Теорема 1.1. Свойство полиномиалъности во вполне автоматной биномиальной алгебре А относительно порядка deglex алгоритмически распознаваемо.

Теорема 1.2. Пусть А — К.(Х)/1 - вполне автоматная биномиальная алгебра относительно некоторого порядка на мономах. Тогда существует алгоритм, определяющий, является ли А алгеброй с левой и/или правой конечной R -переработкой. Кроме того, алгоритм определяет минимальное такое число R

Теорема 1.3. Любая мономиальная подалгебра свободной ассоциативной алгебры изоморфна вполне автоматной алгебре относительно некоторого порядка < на мономах.

Более того, любая мономиальная подалгебра вполне автоматной биномиальной алгебры относительно порядка <<jegiex также изоморфна вполне автоматной алгебре относительно порядка ~<. Изоморфизм в обоих случаях эффективный

Приведенные теоремы изложены в §1.5 диссертации. В §1.1 определяются понятия вполне автоматных биномиальных алгебр первого и второго типов, стандартно регулярно определенных алгебр, свойства строгой и нестрогой полиномиальное™ и свойства ограниченной степени. В §1.2 содержатся основные утверждения, позволяющие упростить технику работы с регулярными языками над алфавитом, являющимся произведением двух алфавитов В §1.4 приводится классификация полугрупповых и мономиальных алгебр Здесь же определяются эквивалентные способы задания вполне автоматных алгебр обоих типов, рассматривается случай, когда классы вполне автоматных алгебр первого и второго типа совпадают. Приводятся необходимые примеры

,0J. MAnson, Р Nordbeck, Regular Grobner bases // Symbolic computations, no. 33, 163-181, 2002.

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

Основными результатами главы являются следующие две теоремы, изложенные в §2.2 и §2 3 соответственно.

Теорема 2.1 Левый модуль сизигий Eg систем элементов <7ъ ■■■ ,9т автоматной мономиальной алгебры А совпадает с линейной оболочкой над полем К множества Т = I J (£!5iF[rfi).

Теорема 2.2 Множество G = U[d]eK(r4) является базисом

Гребнера левого идеала I = Agi + ... + Agm .

В этих теоремах индексы [ci] пробегают все вершины единственного минимального конечного детерминированного автомата Г^, задающего регулярный язык ненулевых слов автоматной мономиальной алгебры А, С Ат — некоторые множества наборов (Д,..., /т), с условием deg /, < m * |У(Гл)| * r(maxi<;;-<rm(deg, G^ — некоторые множества элементов / идеала I степени deg/ < maxi^J^m(deg^1) *m* |V(r/1)|*r(H-max1.<::i<m(deg5i)). Здесь r(k) —росталгебры А, V(TA) — число состояний автомата Г л, а под степенью deg понимается длина максимального монома при степенной упорядоченности Последние два неравенства свидетельствуют об ограниченности всех множеств Fда и

В §2.4 с помощью приведенных конструкций решаются следующие алгоритмические проблемы: распознавание принадлежности элемента левому конечно порожденному идеалу, вычисление коэффициентов представления этого элемента в виде линейной комбинации порождающих идеала; нахождение общего решения линейного уравнения; нахождения пересечения двух левых конечно порожденных идеалов; распознавание свободного левого конечно порожденного модуля

В третьей главе рассматриваются конечно порожденные ассоциативные алгебры А = fC(X)/I, обладающие свойством конечномерности пространства лиевых элементов. Рассмотрим подпространство L линейного АС-пространства ÎC(X), являющееся свободной алгеброй Ли с порождающими из X. Тогда множество L = {f + I \ f € L} С А является подпространством линейного 1С-пространства А и называется пространством лиевых элементов алгебры А. Основной результат главы сформулирован в следующих двух теоремах

Теорема 3.1 Пусть для конечно определенной ассоциативной алгебры А = 1С(х1,..., хп)/1 подпространство Ь С А представляет собой пространство лиевых элементов алгебры А и Ь — Ярап^з;! + I,... ,хп +1), тогда существует такая невырожденная линейная замена образующих Х{, что идеал соотношений образовавшейся алгебры имеет конечный базис Гребнера, эффективно строящийся по определяющим соотношениям идеала I.

Теорема 3.2 Конечно определенная ассоциативная алгебра с конечномерным пространством лиевых элементов эффективно изоморфна конечно определенной ассоциативной алгебре, идеал соотношений которой обладает конечным базисом Гребнера.

Теорема 3.1 обобщает результат Д.Айзенбуда, И.Пеевой и Д Штурмфельса11 о поднятии базиса Гребнера идеала соотношений коммутативной алгебры до базиса Гребнера идеала соотношений некоммутативной ассоциативной алгебры.

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

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

Теорема 4.1 Пусть А — ненулевая конечно-порожденная автоматная мономиалъная алгебра и В — подалгебра алгебры , заданная своим конечным БАйВI-базисом V = {/ь • • •, /т} • Тогда алгоритмически распознаваемо свойство алгебры В быть свободной подалгеброй алгебры со свободными порождающими /1, • • ■, /т

Теорема 4.2 Существует алгоритм проверки алгебраической зависимости конечного числа однородных полиномов одинаковой степени конечно-порожденной свободной алгебры.

Теорема 4.1 является обобщением аналогичного результата Л.Касапенко12 для конечно определенных мономиальных алгебр

Автор выражает глубокую благодарность своему научному руководителю, профессору В. Н. Латышеву, за постановку задач и помощь в работе.

"David Eisenbud, Irena Peeva, Bernd Sturmfels Non-commutative Gröbner bases for commutative algebras // Proceedings of the American Mathematical Society 1998. Vol. 126 Num. 3. P. 687-690.

David Eisenbud Commutative Algebra With a View Toward Algebraic Geometry // SpringerVerlag. NY. 1995. P. 351-358.

"Касапенко Л Ю. О paспознаваемых свойствах ассоциативных алгебр // Канд. дис. Ульяновск, 2000.

Работы автора по теме диссертации.

• С. А. Илясов, Построение модуля сизигий автоматной мономи-альной алгебры // Фунд. и прикл. матем., т. 11, вып. 2, 2005, с 101-113.

• С. А Илясов, Распознавание алгебраической зависимости в конечно порожденных алгебрах // Вестник МГУ, Сер 1. Математика. Механика, N 2, 2005, с 27-32.

• С. А Илясов, Вполне автоматные алгебры // Москва, 2005, деп. в ВИНИТИ № 912-В2005, 25 с.

• С. А. Илясов, Базисы Гребнера в идеалах соотношений алгебр, в которых лиевы элементы образуют конечномерное пространство // Москва, 2005, деп. в ВИНИТИ № 1283-В2005, 12 с.

Подписано о печать 63. С'3.0£> Формат 60x84/16. Усл.псч.л. О, Ь Тираж /ОС экз. Заказ 2. 4 Отпечатано в Отделе лечат» МГУ

I

1 »

1 í

I

I >

Í

3 34 0

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 Распознавание алгебраической зависимости элементов автоматной мономиальной алгебры, образующих

S AG ВI-базис порождаемой ими подалгебры.

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

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

Главным отличием регулярных языков, представляющих собой множество нормальных слов некоторой автоматной алгебры, является то, что каждое подслово некоторого слова этого языка снова принадлежит языку. Тем не менее, для работы с автоматными алгебрами зачастую достаточно общего определения регулярного языка, так как регулярные языки обладают достаточным количеством свойств, позволяющих производить практически любые манипулирования с ними. Наиболее стандартные свойства описываются в [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), распознавание правой и/или левой конечной переработки (теорема 1.2), построение определяющего регулярного языка для алгебры с конечной переработкой (предложение 1.2) и для мономиальных подалгебр свободной ассоциативной алгебры и некоторых вполне автоматных алгебр (теорема 1.3).

2) Строится левый модуль сизигий конечной системы элементов автоматной мономиальной алгебры А и базис Гребнера конечно порожденного левого идеала (теоремы 2.1 и 2.2). Решаются алгоритмические проблемы: распознавания существования нетривиального решения линейного уравнения над А с конечным числом неизвестных — элементов из А (предложение 2.1), распознавания вхождения элемента в конечно порожденный левый идеал (предложение 2.2), построения семейства порождающих пересечения двух конечно порожденных левых идеалов (предложение 2.3), распознавания того, является ли конечно порожденный левый Л-модуль свободным (предложение 2.4).

3) Строится эффективный изоморфизм алгебры с конечномерным пространством лиевых элементов на стандартно конечно определенную алгебру (следствие 3.2). В случае, когда размерность этого пространства совпадает с количеством образующих, приводится алгоритм, строящий такую невырожденную линейную замену образующих, что идеал соотношений алгебры, полученной в результате этой замены, обладает конечным базисом Гребнера (следствие 3.1).

4) Для подалгебр, заданных конечным SAGBI -базисом в автоматной мономиальной алгебре положительно решен вопрос об алгоритмическом распознавании алгебраической зависимости порождающих подалгебры (теорема 4.1). Указан алгоритм распознавания алгебраической зависимости однородных полиномов одинаковой степени в свободной ассоциативной алгебре (следствие 4.1).

Для изложения подробных результатов диссертации введем необходимые обозначения и определения.

Пусть К— поле нулевой характеристики; X = {xi,.,xn} — произвольный алфавит; (X)— свободная полугруппа, порожденная множеством X; /С (X) — алгебра некоммутативных полиномов или свободная ассоциативная алгебра над полем /С с системой образующих (или порождающих) X.

Элементы полугруппы (X) называются некоммутативными мономами или словами, а элементы /С {X) — некоммутативными полиномами.

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

Заметим, что произвольная ассоциативная алгебра А = 1С(Х)/1 изоморфна алгебре некоммутативных полиномов 1С(Х) с умножением / о д = nor(fg), где nor(fg) — нормальная форма произведения fg относительно идеала X. Поэтому элементы ассоциативной алгебры мы будем иногда называть полиномами (мономами или словами).

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

В любом ненулевом полиноме /, нормальном относительно идеала определяющих соотношений, можно выделить старший член /, наибольший среди всех мономов элемента / в данном порядке. Если полином / не является нормальным, то через / обозначим старший член полинома nor(/).

Некоторые множества слов ассоциативной алгебры, порожденной конечным алфавитом X, могут образовывать регулярный язык. Такое множество может быть задано конечным автоматом, который мы всегда будем мыслить как ориентированный маркированный граф, некоторые вершины которого объявлены начальными, а некоторые — конечными. Иногда вершины такого графа мы будем называть состояниями автомата. Обозначим через © множество вершин автомата, а через 2х — множество всех подмножеств конечного алфавита X. Вместо ребер, ведущих из вершины 0\ 6 0 к вершине 02 £ © и маркированных буквами X(v ., Xik, мы часто будем пользоваться понятием функции перехода § : © х © —> 2х из состояния в\ в состояние 02:

3(01,02} = где Xii,.,Xik — буквы-маркеры ребер, ведущих из вершины 0\ € © к вершине 02 G ©. Таким образом, конечный автомат может быть задан не только ориентированным маркированным графом, но и пятеркой (X, 0, ©о, ©а, , где X — конечный алфавит, © — множество состояний (вершин) автомата, ©о — множество начальных состояний автомата, ©а — множество конечных состояний автомата, 5 — функция переходов.

Каждому конечному автомату соответствует некоторое множество слов в алфавите X. Эти слова соответствуют путям в графе из некоторой начальной вершины в некоторую конечную вершину. Слова образуются "приписыванием"справа буквы-маркера текущего ребра.

Множество слов, задаваемое конечным автоматом, принято называть регулярным языком.

Определение 1. Для данного конечного автомата К а , изображаемого ориентированным маркированным графом Гд, и соответствующего ему регулярного языка La рассмотрим множество путей графа Г^, начинающихся в начальных его состояниях, а заканчивающихся в состоянии в. Через Сц обозначим множество слов, соответствующих этим путям.

Аналогично определяем Cgnt как множество слов, соответствующих путям, начинающимся в в и заканчивающихся в конечных состояниях Гл, а также как множество слов, соответствующих путям, начинающимся в состоянии в, а заканчивающимся в состоянии в1.

Отметим, что С10 , С^ и Cf,e суть регулярные языки. Они задаются автоматами, образованными из Гд объявлением единственной конечной (для in и io) вершины в и начальной (для out и io) вершины 9' как множества конечных (соответственно начальных) вершин.

Обозначим Cf = С>1д.

Рекурсивно определим понятие регулярного выражения над X:

1) 0 — регулярное выражение

2) Для любого х € X х — регулярное выражение

3) Для любых двух регулярных выражений г\ и 7*2 Г\Г2 и г\ U 7*2 — регулярные выражения.

4) Для любого регулярного выражения г г* — регулярное выражение.

Каждое регулярное выражение определяет некоторое множество слов в алфавите X. Если регулярные выражения г\ и Г2 определяют множества слов R\ и i?2, то регулярные выражения Г\Г2, Г\ U 7*2, г\ определяют множества слов R1R2, Ri U R2 и (J^0 R\ соответственно.

Известная теорема Клини утверждает, что любой регулярный язык может быть задан некоторым регулярным выражением, и что любое регулярное выражение определяет некоторый регулярный язык.

Определим понятие обобщенного регулярного выражения, для которого будет справедлив аналог теоремы Клини.

Определение 2. Обобщенным регулярным выражением называется выражение, полученное из регулярных следующим образом. Если г\ и г2 — регулярные или обобщенные регулярные выражения, то г\ U г2, г 1Г2, г\ , 7*1 \ 7*2 и 7*1 П 7*2 также обобщенные регулярные выражения.

Обобщенные регулярные выражения тоже определяют некоторые множества слов в алфавите X. Если обобщенные регулярные выражения 7*1 и 7*2 определяют множества слов R\ и R2, то обобщенные регулярные выражения т\ \ 7*2 и г\ П 7*2 определяют множества слов R\ \ R2 и R\ П R2 соответственно. Часто мы будем обозначать множество, определяемое некоторым обобщенным регулярным выражением, тем же символом, что и само обобщенное регулярное выражение.

Известно (см [5]), что дополнение L' = X* \ L любого регулярного языка L в алфавите X, является регулярным языком. Поэтому разность и пересечение двух регулярных языков также будут регулярными языками с регулярными выражениями L\\L2 = (L1UL2)' и Ь\ П L2 = (L[ U Ь'2)' соответственно.

Тогда имеет место очевидное утверждение.

Предложение 1 (Аналог теоремы Клини). Любой язык, задаваемый конечным автоматом, может быть задан обобщенным регулярным выражением. Любой язык, задаваемый обобщенным регулярным выражением, может быть задан конечным автоматом.

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

Определение 3. Для любого регулярного языка L в алфавите X языком обструкций языка L называется множество слов O(L), не имеющих собственных подслов в языке L.

Определение 4. Множество М :r L = {и £ X* \ uL П М ф 0} называется слабым правым делением регулярного языка М на регулярный язык L в алфавите X. Аналогично определим слабое левое деление М :i L — {и G X* | Z/u П М ^ 0}, сильное правое деление М -fr L = {и £ X* \ uL С М} и сильное левое деление М ~i L = {и е X* | Lu С М}.

Для любого регулярного языка L через Ki обозначим некоторый конечный автомат, задающий язык L. Через V(K) будем обозначать множество состояний конечного автомата К.

Для любого монома и ассоциативной алгебры через degu обозначим длину монома и, называемую его степенью.

Определение 5. Назовем ассоциативную алгебру А = /С(Х)/1 (полугруппу М) алгеброй (полугруппой) с левой R-переработкой, если существует число R ^ 0, такое, что для всех нормальных мономов p,q Е А (для всех нормальных слов p,q Е М), q = qiq2, deg <72 = R» выполняется равенство пог(до) = q\ nor(q2p) • Аналогично определяются алгебра и полугруппа с правой R-переработкой.

Перейдем к подробному изложению работы. Диссертация состоит из 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 рассматриваются конечно порожденные ассоциативные алгебры А = К{Х)/1 над полем /С нулевой характеристики, удовлетворяющие следующему условию.

Рассмотрим подпространство L линейного /С-пространства JC(X), где подпространство L является свободной алгеброй Ли с порождающими из X. Тогда множество L = {/ + / | / G L} С А является подпространством линейного /С-пространства А. Рассматриваются алгебры А с условием конечномерности пространства L.

В §3.1 на алгебру А накладываются некоторые условия, при выполнении которых приводится алгоритм, строящий конечное число элементов базиса Гребнера конечно порожденного идеала определяющих соотношений алгебры А, степень которых не превышает заданного числа. Показывается, что алгебра А автоматная, и описывается регулярный язык нормальных слов автоматной алгебры А.

Эти условия выполняются, в частности, когда L = Span^rr + I | х £ X). В §3.2 в этом случае приводится алгоритм нахождения такой невырожденной линейной замены образующий, что идеал соотношений полученной в результате этой замены алгебры обладает конечным базисом Гребнера.

Здесь же рассматривается общий случай алгебры с конечномерным пространством лиевых элементов и строится изоморфизм этой алгебры на стандартно конечно определенную алгебру (следствие 3.2).

В главе 4 решаются алгоритмические проблемы, связанные с распознаванием алгебраической зависимости элементов определенного вида в некоторых ассоциативных алгебрах. Отметим, что в свободной конечно-порожденной алгебре У. У. Умирбаевым (см. [10]) получено отрицательное решение проблемы распознавания алгебраической зависимости конечного числа элементов, поэтому приходится ограничиваться частными случаями элементов определенного вида.

В §4.1 основным утверждением является теорема 4.1, в которой разрешается проблема алгоритмического распознавания алгебраической зависимости конечного числа элементов автоматной мономиальной алгебры, порождающих SAGBI-подалгебру. Этот результат обобщает результат Л.Касапенко ([11, с. 28-31]) о распознавании этого же свойства в конечно определенной мономиальной алгебре. Предложение 4.2 заимствовано из работы Касапенко, и его доказательство дословно переносится на случай автоматной мономиальной алгебры.

В §4.2 предложение 4.3 является ключом к обоснованию своего следствия 4.1 и определяет алгоритм распознавания алгебраической зависимости конечного числа однородных элементов одинаковой степени свободной ассоциативной алгебры.

Автор выражает глубокую благодарность своему научному руководителю, профессору В. Н. Латышеву, за постановку задач и помощь в работе.

1. В. Н. Латышев, Комбинаторная теория колец. Стандартные базисы., МГУ, 1988, 68с.

2. Thomas Becker, Volker Weispfenning, Grobner Bases, Springer-Verlag, 1993.

3. А. Я. Белов, В. В. Борисенко, В. Н. Латышев, Мономиальные алгебры, Итоги науки и техники, сер. Современная математика и ее приложения, Тематические обзоры, т. 26, с. 35-214, Москва, 2002.

4. Д. И. Пионтковский, Некоммутативные базисы Гребнера, когерентность ассоциативных алгебр и делимость в полугруппах, Фундаментальная и прикладная математика, т. 7, н. 2, с. 495-513, Москва, 2001.

5. А. Саломаа, Жемчужины теории формальных языков, Мир, 1986.

6. J. Manson, P. Nordbeck, Regular Grobner bases, Symbolic computations, no. 33, 163-181, 2002.

7. А. Я. Белов, Линейные рекуррентные уравнения, International University of Bremen, Moscow Institute of Open Education, 2003.

8. David Eisenbud, Irena Peeva, Bernd Sturmfels, N on-commutative Grobner bases for commutative algebras, Proceedings of the American Mathematical Society. 1998. Vol. 126. Num. 3. P. 687-690.

9. David Eisenbud, Commutative Algebra With a View Toward Algebraic Geometry, Springer-Verlag. NY. 1995. P. 351-358.

10. У. У. Умирбаев, Некоторые алгоритмические вопросы ассоциативных алгебр, Алгебра и логика. 1993. 32, № 4, 450470.

11. JI. Ю. Касапенко, О распознаваемых свойствах ассоциативных алгебр, Канд. дис. Ульяновск, 2000.

12. С. А. Илясов, Построение модуля сизигий автоматной мономиальной алгебры, Фунд. и прикл. матем., т. 11, вып. 2, 2005, с 101-113.

13. С. А. Илясов, Распознавание алгебраической зависимости в конечно порожденных алгебрах, Вестник МГУ, Сер 1. Математика. Механика, N 2, 2005, с 27-32.

14. С. А. Илясов, Вполне автоматные алгебры, Москва, 2005, деп. в ВИНИТИ № 912-В2005, 25 с.

15. С. А. Илясов, Базисы Гребнера в идеалах соотношений алгебр, в которых лиевы элементы образуют конечномерное пространство, Москва, 2005, деп. в ВИНИТИ № 1283-В2005, 12 с.