Допустимые упорядочения и стандартные базисы дифференциальных идеалов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Московский государственный университет имени М.В. Ломоносова

Механико-математический факультет

На правах рукописи УДК 512.628.2+519.688

Зобнин Алексей Игоревич

003053153

Допустимые упорядочения

и стандартные базисы дифференциальных идеалов

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2007

003053153

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

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

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

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

кандидат физико-математических наук, ведущий научный сотрудник Е.В. Панкратьев

доктор физико-математических наук, профессор A.A. Михалев кандидат физико-математических наук, доцент И.Н. Балаба Вычислительный центр РАН им. A.A. Дородницына

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

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

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

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

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

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

Дифференциальные стандартные базисы, появившиеся в немного отличающихся формах в конце 1980-х гг. в работах Ф. Оливье* и Дж. Kappa Ферро4-, являются прямым и естественным обобщением понятия базиса Гребнера, но не позволяют полностью решить задачу принадлежности. Сами основатели теории подметили, что для многих идеалов они могут быть

'Becker Т. and Weiípfenning W., Groelmer Batet. A Computational Approach to Commutative Algebra, Graduate Texts In Mathematics, Springer-Verlag, New York, 1993.

'Gallo G., Mishra В., Ollivier F., Some Constructions in Rings of Differential Polynomials, Lecture Notes in Computer Science, vol. 539, 171-182, 1991.

1 Ollivier P., Standard Bates of Differential Ideals, Lecture Notes in Computer Science, 304-321, 508, 1990.

4 Carrb Ferro G., Groelmer Bases and Differential Algebra, Lecture Notes in Computer Science, vol. 356, 129-140, 1989

бесконечными. Этот факт на несколько лет приостановил дальнейшие исследования в этой области. Однако диссертантом были получены неожиданные примеры конечных дифференциальных стандартных базисов, что снова возродило интерес к данной теме. Поводом для исследования стала обнаруженная автором связь между процессом редукции Г. Левй5, дающим алгоритм проверки принадлежности монома идеалу [у*], и появившимися почти через 50 лет дифференциальными стандартными базисами Оливье и Kappa Ферро. Долгое время считалось, что стандартные базисы Оливье и Kappa Ферро даже таких несложно устроенных идеалов, как [у*], являются бесконечными. Однако выяснилось, что при более общих упорядочениях идеалы вида [ур] приобретают конечный дифференциальный стандартный базис {у*}. Такие общие упорядочения (например, degrevlex) являются вполне естественными при вычислении базисов Гребнера полиномиальных идеалов. В то же время в дифференциальном случае они не обладают некоторыми свойствами согласованности с дифференцированиями, и потому не рассматривались основателями теории дифференциальных стандартных базисов. Грубо говоря, Оливье и Kappa Ферро применяли лишь упорядочения lex и deglex.

Цель работы

Целью работы является изучение допустимых упорядочений и критериев конечности дифференциальных стандартных базисов идеалов обыкновенного кольца дифференциальных многочленов ^{у) над полем констант Т нулевой характеристики. Перед автором стояли следующие задачи:

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

• изучить различные классы упорядочений на дифференциальных мономах в зависимости от их связи с дифференцированиями, а также соотношения между этими классами;

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

5 Levi H., On the Structure of Differential Polynomial! and on Thetr Theory of Ideals, Trans. A MS, vol. 51, 532-368, 1942.

• установить необходимые и достаточные условия конечности дифференциальных стандартных базисов при определенных упорядочениях;

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

• изучить поведение дифференциальных стандартных базисов и задачу о принадлежности дифференциального многочлена идеалу при композиции многочленов.

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

Научная новизна данной работы состоит в следующем:

1. Изучены допустимые упорядочения дифференциальных мономов. Доказана полная упорядоченность множества дифференциальных мономов относительно таких упорядочений. Предложено описание упорядочений на дифференциальных мономах в терминах согласованного набора мономи-альных матриц (а также с помощью «бесконечных» матриц особого вида). Выделены различные классы упорядочений в зависимости от их связи с дифференцированиями. Исследован феномен сокращения мономов в производных многочлена. Предложен и реализован в системе компьютерной алгебры Maple 10 алгоритм, строящий дифференциальный многочлен (если он существует), в котором сокращается заданная в общем виде последовательность мономов.

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

3. Получена связь между дифференциальными стандартными базисами и базисами Гребнера полиномиальных идеалов в кольце многочленов от конечного числа производных основной переменной. С помощью этой техники результаты X. Хонга6,7 о поведении базисов Гребнера при композиции многочленов обобщены на дифференциальный случай. Исследована

' Hong H., Groebner Barit Under Composition I, The Journal of Symbolic Computation, 643-663, 25 (S), 1998.

7 Hong H., Groebner Ваш Under Composition //, in Proceeding» of ISSAC-I996, 79-85,1996.

(совместно с М .В. Кондратьевой) задача принадлежности многочлена дифференциальному идеалу, порожденному композицией многочленов: ее решение сведено к решению более простой (с алгоритмической точки зрения) задачи принадлежности.

Основные методы исследования

В работе используются методы и результаты теории базисов Гребнера, коммутативной алгебры, дифференциальной алгебры. Результаты диссертации опираются на работу Леви о структуре дифференциальных многочленов, на статьи Карра Ферро4,8 и Оливье3 о стандартных базисах дифференциальных идеалов («дифференциальных базисах Гребнера»), теорию дифференциальной размерности9,10,11, работу Колчина об экспонентах дифференциального многочлена первого порядка12, теорию Хуна Хонга о поведении базисов Гребнера при композиции многочленов'7, а также предложенную Роббьяно и развитую затем Вайспфеннингом и Хонгом классификацию мо-номиальных упорядочений с помощью матриц13,14,15. Кроме того, автором проведены многочисленные компьютерные вычисления с помощью современных систем компьютерной алгебры. Благодаря этим вычислениям получили подтверждение различные гипотезы, впоследствии доказанные в виде теорем.

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

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

" Carrk Ferro G., Differential GrSbner Вазе» in One Variable and in the Partial Case, Math. Comput. Modelling, Pergamon Press, vol. 25, 1-10, 1997.

'Kolchin E.R., Differential Algebra and Algebraic Group*, Academic Press, 1973.

'"Kondratieva M.V., Levin А.В., MikhaJev A.V., Pankratiev E.V., Differential and Difference Dimension Polynomials, Kluwer Academic Publisher, 1999.

"Kredel H., Weiapfenning V., Computing Dimension and Independent Set for Polynomial Ideals, Journal of Symbolic Computation, vol. 6, 231-247, 1988.

"Kolchin E.R. On the exponents of differential ideals, Annals of Mathematics, 42:740-777, 1941.

13 Robbiano L., On the Theory of Graded Structures, The Journal of Symbolic Computation, 2,139-170, 1986.

14 Weiapfenning V., Differential Term-Orders, in Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, 245-253, ACM press, Kiev, 1993.

15 Hong H. and Weiapfenning V., Algorithmic Theory of Admissible Term Orders, preprint, 1999. http://www4 nesu.edu:8030/"hong/papers/Hong99c.dvi.

циальному идеалу, а также исследовать строение такого идеала. Решение подобных задач связано с исследованием систем нелинейных обыкновенных алгебраических дифференциальных уравнений. Методы и алгоритмы, предложенные в диссертации, могут быть внедрены в существующие системы компьютерной алгебры (автор реализовал эти алгоритмы в системе компьютерной алгебры Мар1е 10). Результаты диссертации могут быть полезны специалистам из Московского государственного университета, Новосибирского государственного университета, Тульского государственного педагогического университета, Вычислительного центра РАН, Объединенного института ядерных исследований.

Апробация работы

Результаты диссертации докладывались:

• на научно-исследовательском семинаре и на семинаре «Кольца и модули» кафедры высшей алгебры МГУ;

• на выездных заседаниях международного семинара по компьютерной алгебре в г. Дубна в 2003, 2004, 2005 и 2006 гг.;

• на международных конференциях «Компьютерная алгебра в символьных вычислениях» (САБС), Ялта, 2002, и Санкт-Петербург, 2004;

• на международной алгебраической конференции,- посвященной 250-летию МГУ и 75-летию кафедры высшей алгебры, МГУ, 2004 г.;

• на конференции «Ломоносовские чтения» в МГУ в 2005 и 2006 гг.;

• на международном симпозиуме по символьным и алгебраическим вычислениям (188АС-2005), Пекин, Китай, 2005 г.;

• на международном семинаре по компьютерной алгебре и информатике, МГУ, 2005 г.;

• на международной конференции «Базисы Гребнера в символьном анализе» (02) в рамках Специального семестра по базисам Гребнера в г. Линц, Австрия, 2006 г.;

• на IX международной конференции «Интеллектуальные системы и компьютерные науки», МГУ, 2006 г.

Публикации

Результаты автора по теме диссертации опубликованы в 9 работах, список которых приводится в конце автореферата.

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

Диссертационная работа состоит из 6 глав (одна из которых является вводной). заключения, приложения и библиографии (66 наименований). Общий объем диссертации составляет 120 страниц.

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

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

Во второй главе приводятся необходимые сведения о мономиальных упорядочениях, их классификации с помощью мономиальных матриц13'15, базисах Гребнера полиномиальных идеалов16 и о поведении базисов Греб-нера при композиции многочленов!5,7.

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

Пусть 71 — алгебра Ритта (т.е. дифференциальное кольцо, содержащее <2) с множеством элементарных коммутирующих дифференциальных операторов Д и © — моноид, порожденный Д. Пусть V — {г^... ,ип} — набор независимых переменных. Кольцом дифференциальных многочленов над И называется кольцо многочленов

П{У} = .....«„} := Щвуи©г/„]

от бесконечного числа дифференциальных переменных вида вь^ = 6°1... На переменных дифференцирования в Р{у) определены стандартным образом: =

Линейный порядок -< на множестве мономов кольца Р{у} называется допустимым упорядочением, если выполнены свойства:

[01.] Р-<Ч Ур,д,зеМ;

[02.] УреМ;

[ОЗ.] ограничение -< на подмножество дифференциальных переменных ©V является допустимым ранжиром: -< 02у, вв\у{ -< вв^у^ и Уг вyi для всех у„ Уу е ©V, 0 6 0.

"Кокг Д., Литтл Дж., О'Ши Д., Идеалы, многообразия и алгоритмы, М., Мир, 2000.

Пусть зафиксировано некоторое допустимое упорядочение -<. Множество S С I называется дифференциальным стандартным базисом идеала I относительно -<, если 65 является (бесконечным) алгебраическим базисом Гребнера идеала /, рассматриваемого в кольце ^[6V]. Дифференциальные стандартные базисы в T{V) можно рассматривать как удобную параметризацию бесконечных базисов Гребнера (алгебраических стандартных базисов) в кольце T[QV\. Эта параметризация обеспечивается дифференциальными операторами и является совместимой со структурой дифференциального кольца ^{V}. Таким образом, мы можем работать с одним элементом / вместо целого семейства ©/.

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

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

Далее рассматривается случай обыкновенного кольца дифференциальных многочленов !F{y}. Для упорядочений на мономах такого кольца предложена матричная классификация. Набор мономиальных матриц{Мк} называется согласованным, если Мк-1 получается из Мк удалением правого столбца и затем откидыванием нулевой строки, если такая найдется. Каждая матрица Мк имеет fc+1 столбцов и задает мономиальное упорядочение на мономах от уо,..., Ук по правилу

В частности, ее столбцы лексикографически неотрицательны.

Теорема 1. Всякое допустимое упорядочение на дифференциальных мономах можно задать согласованным набором мономиальных матриц {Л^к} (матрица {.М*} задает ограничение -< на мономы от Уо,---,Ук), или, что эквивалентно, «бесконечной» (вообще говоря, вверх, вниз и вправо) мономиальной матрицей.

Под «бесконечной» мономиальной матрицей здесь понимается упорядоченная счетная система бесконечных строк с действительными элементами, такая, что для любого fc > 0 в подматрице из первых к + l столбцов лишь конечный набор строк ненулевой, причем этот набор образует мономиаль-ную матрицу упорядочения Тогда, обозначив этот набор через Мк, мы получаем согласованную систему {-М*}-

Пример. Упорядочения lex и degrevlex можно задать соответственно «бесконечными» матрицами

1 ...

1

1

. 1

1 .

1

\х

В работе предложен алгоритмический способ построения канонического согласованного набора матриц для допустимого упорядочения. Так, для порядка degrevlex таким набором будет

(1)

п х 1 1\

0X11 0 0 11 Vo о о 1/

где жирным шрифтом обозначены добавленные на очередном шаге в матрицы строка и столбец. Аналогично в работе определяются упорядочения (у^->^е§)тугеу1ех, degwtгevlex, wtdegгevlex, совершенно естественно возникающие при работе с дифференциальными многочленами.

Пусть р > 0. Моном М = П?«оУГ называется <хр-мономом, если для всех г от 1 до Л выполнено а<_1 Ч-а; < р. Все остальные мономы называются Рр-мономами. Многочлен / называется квазилинейным относительно -<, если / € Т или deglm^ / = 1. Допустимое упорядочение -< называется:

• 6-лексикографическим, если 1т _< 6М = 1ш|ех 5М Ш ф 1;

• 6-фиксированным, если V/ € Р{у} \ Т найдутся такие моном М и индексы ко и г, что 5к/ = Муг+к для всех к > ко\

• ¡3-упорядочением, если 1тч бкуп = 1т<1е8геу1ех 6куп Vк,п ^ 1 (то есть, старший моном <5*уп является /3„-мономом);

• согласованным с квазилинейностью, если производная любого -«-квазилинейного многочлена сама является -<-квазилинейной.

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

Пример. Упорядочения lex, deglex и wtlex являются ¿-лексикографическими. Упорядочения degrevlex, degwtrevlex и wtdegrevlex являются /^-упорядочениями. Все перечисленные упорядочения согласованы с квазилинейностью. Каждое ¿-лексикографическое упорядочение является ¿-фиксированным и согласованным с квазилинейностью.

В конце четвертой главы приведены примеры многочленов, у которых ^-старший моном производных не является/3-мономом. Это явление, невозможное при ¿-лексикографических упорядочениях, рассматривается в более общей форме как сокращение мономов в производных многочленов.

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

Теорема 2 (необходимое условие конечности). Пусть -< — 5-фиксированное упорядочение. Если собственный идеал1<Зг{у} обладает конечным дифференциальным стандартным базисом G относительно -<, то в I содержится -<-квазилинейный многочлен.

Эта теорема для лексикографического упорядочения (а также для случая нескольких дифференцирований) была впервые.доказана Дж. Kappa Ферро8. В данной работе она модифицирована и обобщена на случай более общих упорядочений.

Теорема 3 (достаточное условие конечности). Пусть -< согласовано с квазилинейностью. Если в собственном дифференциальном идеале I < F {у} имеется -<-квазилинейный многочлен, то дифференциальный стандартный базис идеала I относительно -< является конечным.

Следствие 1. Пусть -Ч — S-лексикографическое упорядочение. Для того, чтобы дифференциальный стандартный базис собственного идеала 1<Р{у} был конечным, необходимо и достаточно, чтобы в / содержался -<-квазилинейный многочлен.

Следующий факт определяет ключевую роль порядка lex:

Теорема 4. Если идеал обладает конечным дифференциальным стандартным базисом при S-фиксированном упорядочении, то он обладает конечным стандартным базисом и при лексикографическом упорядочении.

Из доказанных теорем вытекают следующие результаты:

Следствие 2. Следующие условия эквивалентны:

• идеал I <J-{y} обладает конечным лексикографическим дифференциальным стандартным базисом;

• el содержится \ех-квазилинейный многочлен;

• факторалгебра F[y,y\,yi, • •.]// конечно порождена.

Следствие 3. Следующие условия эквивалентны:

• идеал I<F{y} обладает конечным дифференциальным стандартным базисом относительно упорядочения deglex;

• в I содержится линейный многочлен.

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

Улучшенный процесс Оливье Вход:

F С F{y) — конечное множество дифференциальных многочленов

(образующих идеала); -< — ¿-фиксированное и согласованное с квазилинейностью допустимое упорядочение. Выход:

Редуцированный дифференциальный стандартный базис идеала [F] (в случае, если он конечен). G := F; Я := 0; s := max/gf ord /; k := 0; repeat Gold 0; while G Ф Gou do Я := Diff Complete (G, s + A:); G0id •= G;

G := ReducedGröbnerBasis (Я, -<); end do; k:=k + l\ until ContainsQuasiLinear (G, -<); return DiffAutoreduce (G, -<);

,7Ои называется «улучшенным процессом Оливье» в отличие от обычного процесса Оливье3, который мог hp остановиться даже я случае конечного стандартного базиса.

Стандартная функция ReducedGrobnerBasis (Я, -<), используемая в этом процессе, возвращает редуцированный базис Гребнера идеала (Я) относительно -< в кольце многочленов от всех переменных, от которых зависят элементы Я. DifFComplete (G,r) возвращает множество, состоящее из всех элементов G и их производных, лежащих в ^"[í/o.í/i, • ■ • ,2/г]. Алгоритм DiffAutoreduce (G, -<) редуцирует каждый элемент д 6 G относительно производных элементов mG\{g}. Функция ContainsQuasiLinear (G, -<) проверяет наличие в множестве G -<-квазилинейного многочлена.

В работе доказано, что улучшенный процесс Оливье завершает работу тогда и только тогда, когда [F] обладает конечным дифференциальным стандартным базисом при ¿-лексикографическом допустимом упорядочении -<, согласованном с квазилинейностью. При этом он возвращает редуцированный дифференциальный стандартный базис идеала [F].

Далее в работе изучаются условия конечности дифференциальных стандартных базисов при /^-упорядочениях.

Предложение 1. Идеал [yn], n > 1, обладает конечным дифференциальным стандартным базисом {уп} относительно ~< в том и только том случае, когда -< — /?-упорядочение.

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

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

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

(Дифференциальной) композицией с дифференциальным многочленом V называется дифференциальный эндоморфизм F{y) —* ^{у}, при котором у ь-» ф. Образ многочлена / € F{y} при дифференциальной композиции обозначается через / оф. Через Hi обозначается кольцо многочленов Т[у,у\,.. .,1/,], а через -<,• — ограничение упорядочения -< на мономы из Я,. Запись DSB_<(S, [F]) будет обозначать условие «S являет-

ся дифференциальным стандартным базисом идеала [F] относительно -<», a DSB4(5) - условие DSB^(S, [S]).

Теорема 5. Пусть -< — допустимое упорядочение на дифференциальных мономах, г^0иф€Ит — дифференциальный многочлен, причем 1тч 6кф = ут+к при всех к ^ 0. Пусть Ф = (у, уи..., уТ-ъ ф, 8ф, ¿Рф,...) и S С ЯУг,!/г+ьУг+2,...] = ?{Уг}- Тогда DSB4(5, [F] < F{y}) DSB4(5o Ф, [Fo$]<if{y}).

Теорема 6. Пусть упорядочение на дифференциальных мономах < является полностью однородным, аф € Т{у) —(-квазилинейный многочлен, причем 1тч 5кф = уг+к для всех к > 0. Тогда

DSB[Л<Лу}) DSBy(5оФ, [Fo Ф] «.Ffj,}).

Развитая в работе техника позволяет доказать следующие важные результаты:

Теорема 7. Пусть -< — согласованное с квазилинейностью 0-упорядочение., Для того, чтобы собственный идеал I обладал конечным дифференциальным стандартным базисом относительно -<, достаточно, чтобы либо I содержал -<-квазилинейный многочлен, либо I порождался некоторой степенью -¿.-квазилинейного многочлена.

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

Теорема 8. Пусть k ^ 0. Тогда найдется упорядочение -<, такое, что для любого лексикографически квазилинейного многочлена f порядка к и любого п > 1 идеал [/п] обладает дифференциальным стандартным базисом из одного /" относительно Ч.

В работе данное упорядочение -< строится явным образом.

В диссертации имеется три приложения. В приложении А приводятся соотношения между классами упорядочений и формулировками основных теорем. Затем изложена реализация в системе компьютерной алгебры Maple 10 улучшенного процесса Оливье (приложение В) и алгоритма, строящего дифференциальный многочлен заданного веса, в производных которого сокращается указанная в общем виде последовательность мономов (приложение С).

Благодарности

Автор благодарит научного руководителя, ведущего научного сотрудника. кандидата физико-математических наук Евгения Васильевича Панкратьева за помощь в выборе темы исследования, внимательное руководство в процессе исследовательской деятельности и множество полезных идей. Автор весьма признателен доктору физико-математических наук, профессору Александру Васильевичу Михалеву, доктору физико-математических наук, профессору Виктору Николаевичу Латышеву, доктору физико-математических наук, профессору Евгению Соломоновичу Голоду и кандидату физико-математических наук Марине Владимировне Кондратьевой.

Автор также выражает благодарность к.ф.-м.н. Елене Игоревне Буниной, к.ф.-м.н. Олегу Голубицкому, Дмитрию Трушину, Алексею Овчинникову и всем участникам семинара по компьютерной и дифференциальной алгебре на механико-математическом факультете МГУ под руководством Е.В. Панкратьева.

Автор глубоко благодарит своих родителей и коллектив кафедры высшей алгебры за поддержку в работе. Автор посвящает работу своим школьным учителям математики: Тамаре Васильевне Симкиной и Елизавете Николаевне Стрелковой.

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

(1] Зобнин А.: О стандартных базисах в кольце дифференциальных многочленов. Фундаментальная и прикладная математика, том 9, вып. 3, стр. 89-102 (2003).

[21 Zobnin А.: Essential Properties of Admissible Orierings and Ranktngs Contributions to General Algebra 14, pp. 205-221 (2004).

[31 Зобнин А.: Обобщенная редукция в кольце дифференциальных многочленов. Программирование, № 30 (2), стр. 42-50 (2004).

[4[ Zobnin А.: Оп Testing the Membership to Differential Ideals. In Proceedings of the 7th International Workshop on Computer Algebra in Scientific Computing (CASC-2004), July 12-19, 2004, St. Petersburg, Russia, pp. 485-496 (2004).

(5) Zobnin A.: Some Results on Differential Grobner Bases. In Proceedings of A3L-2005 (Conference in Honor of the 60th Birthday of Volker Weispfenning), April 3-6, Passau, Germany, pp. 309-314 (2005).

[6| Zobnin A.: Admissible Orderings and Finiteness Criteria for Differential Standard Bases. In Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC-2005), July 24-27, Beijing, China, pp. 365-372 (2005).

[7] Зобнин А.И., Кондратьева M.B.: Задана принадлежности для дифференциальных идеалов, порожденных композицией многочленов. Программирование, № 32 (3), стр. 3-9 (2006).

В данной работе Зобнину А.И. принадлежит доказательство основных результатов (теорема 3, следствия 1, 2 и S) об эквивалентности задачи принадлежности дифференциального многочлена дробному идеалу, порожденному композицией многочленов, и задачи принадлежности соответствующего ргерагайоп-многочлена более простому идеалу. Кондратьевой М.В. принадлежат формулировки этих теорем, а также вычислительные примеры.

[8] Кондратьева М.В., Панкратьев Е.В., Зобнин А.И. й Трушин Д.В.: Вопросы конечности дифференциальных стандартных базисов. Материалы IX международной конференции «Интеллектуальные системы и компьютерные науки», том 1, часть 2, 141-144 (2006).

В данной работе Зобнину А.И. принадлежат построение и реализация в системе компьютерной алгебры Maple *улучшенного процесса Оливьедоказательство теорем 5 и б, а также вычислительные примеры. Трушину Д. В. принадлежит исследование идеала сепарант, а также предложение 1 о связи идеала сепарант и конечности лексикографического дифференциального стандартного базиса. Кондратьевой М.В. и Панкратьеву Е.В. принадлежат постановка задачи, вычислительные примеры, а также гипотезы о связи радикальности однопорожденного дифференциального идеала и конечности его дифференциального стандартного базиса.

[9| Зобнин А.И.: Поведение дифференциальных стандартных базисов при композиции. «Фундаментальная и прикладная математика», том 13, выпуск 1, стр. 109-134 (2007).

Издательство ЦПИ при механико-математическом факультете

МГУ им. М.В. Ломоносова.

Подписано в печать 2S.12.0S

Формат 60 х 90 1 /16 . Усл. печ. л. / О

Тираж 100 экз. Заказ 36

1 Введение

1 1 Актуальность юмы

12 Цель работы

1 3 Научная новизна

1 4 Основные методы исследования

1 5 Teopei ическая и прак1ическая ценность работы

16 Апробация работы

1 7 Публикации

18 CrpyKiypa и обьем диссерхации

1 9 Блаюдарноии

2 Конструктивные методы коммутативной алгебры

2 1 Основные п0ня1ия теории базисов Гребнера И 2 2 Махричное задание мономиальных упорядочений

2 3 Поведение базисов Гребнера при ком по шции

3 Конструктивные методы дифференциальной алгебры

3 1 Основные понятия дифференциальной алгебры . 18 3 2 Задача принадлежности дифференциальному идеалу . 20 3 3 Допустимые упорядочения и ранжиры . .23 3 4 Харакхеристические множества . . 2G 3 5 Дифференциальные С1андар1ные базисы

3 6 Дифференциальные базисы Гребнера

4 Свойства допустимых упорядочений дифференциальных мономов

4 1 Вполне упорядоченность множеава дифференциальных мономов . .30 4 2 Матричное задание дифференциальных мономиальных упорядочений . . 36 4 3 Особые классы дифференциальных мономиальных упорядочений . . 46 4 4 Сокращение старших мономов в производных

5 Дифференциальные стандартные базисы

5 1 Определения Оливье и Карра Ферро . G7 5 2 Необходимое и допаючное условия существования конечных дифференциальных (1андар1ных базисов 70 5 3 Улучшенный процесс Оливье 74 5 4 Конечность дифференциальною стандартного базиса идеала [у"J . . . 79 5 5 Примеры конечных и параметрических дифференциальных с 1андаргных базисов

5 6 Дифференциальные с 1андартые базисы идеала [уу\]

6 Дифференциальные идеалы, порожденные композицией многочленов

6 1 Связь дифференциальных пандаргных базисов с базисами

Гребнера

6 2 Поведение дифференциальных стандартных базисов при композиции . . 92 6 3 Применения теорем о композиции дифференциальных стандартных базисов . 96 6 4 Задача принадлежности для дифференциальных идеалов, порожденных композицией

1.1 Актуальность темы

В последние пятнадцать лет был достигнут значительный прогресс в области компьютерной алгебры Одной из ее приоритетных задач являе1ся развитие методов решения систем нелинейных ал!ебраических уравнений от нес кольких переменных, а 1акже методов изучения ал! ебраических идеалов, порожденных нелинейными полиномиальными сисчемами Настоящим прорывом в данной области стало появление базисов Гребнера и алюритма их вычисления, предложенно1 о Б Бухбертером в середине 1960-х годов [5, 2, 9] Теория исключений, использовавшаяся ранее для решения систем, оказалась час1ыо новой 'теории, позволяющей приводить произвольную систему уравнений к стандартному виду Неудивительно, чю впоследствии стали разрабатываться различные обобщения понятия базиса Гребнера полиномиального идеала на прочие алгебраические структуры.

Одной из таких структур явились дифференциальные идеалы в кольце дифференциальных мноючленов, моделирующие системы дифференциальных ал1 ебраических уравнений в юм же смысле, в каком полиномиальные идеалы моделирую1 сииемы обычных алгебраических уравнений Для радикальных дифференциальных идеалов в кольце дифференциальных многочленов над алгеброй Рит та был создан эффекiивный метод разложения на характеризуемые компоненты [4, 3, 25], позволяющий, в частности, проверив принадлежность дифференциально! о миоючлспа такому идеалу и ииледоваiь строение множества решений Для произвольных бесконечно порожденных дифференциальных идеалов была доказана алгоритмическая неразрешимое!ь задачи принадлежнос1 и [16] Однако для нерадикальных конечно порожденных идеалов вопрос об алгоритмическом решении задачи принадлежности до сих пор открыт.

Дифференциальные стандартные базисы, появившиеся в hcmhoi о отличающихся формах в конце 1980-х гг в работах Ф Оливье [35, 36] и Дж Kappa Ферро [6], являются прямым и естественным обобщением понятия базиса Гребнера, но не позволяю i полное гыо решить задачу принадлежности Сами основатели 1еории подмегили, чю для многих идеалов они могут быть бесконечными 3roi факт на несколько лег приостановил дальнейшие исследования в этой области Однако не так давно автором были получены неожиданные примеры конечных дифференциальных стандартных башсов [59. 63], что снова возродило ишерес к данной теме Автор работы обнаружил связь между процессом редукции Г Леви [30], дающим алгориш проверки принадлежно( 1и монома идеалу [ур], и дифференциальными с тан-дар пшми базисами Оливье и Карра Ферро, появившимися поч1И через 50 ле 1 Долioe время ( чипиюсь, что стандартные базисы бесконечны даже у таких сравнительно просю ус троенных идеалов, как [?/]. Однако выяснилось, что при более общих упорядочениях идеалы вида [ур\ приобретают конечный дифференциальный стандартный базис {ур} Такие общие упорядочения (например, degrevlex) являю i с я вполне ec'Teci венными при вычислении башсов Гребнера полиномиальных идеалов. В ю же время в дифференциальном случае они не обладают иекоюрыми свойствами согласованноеiи с дифференцированиями, и потому не рассматривались основа1елями 1еории Грубо юворя, Оливье и Карра Ферро применяли лишь лексикографическое и сначала по степени, затем лексикографическое упорядочения

1.2 Цель работы

Целью насюящей рабош являе!ся изучение критериев конечности дифференциальных стандартных базисов идеалов обыкновенно!о кольца дифференциальных многочленов F{y} над нолем консишт Т Перед автором возникли следующие задачи

• yciaHOBHjb некоюрые свойства допустимых упорядочений на дифференциальных мономах (например, полноту) без дополнительных предположений о согласованной и с дифференцированиями; описчиь всевозможные 1акие упорядочения некоторым коне фукхивным способом, аналогичным мафичному заданию обычных мономиальных упорядочений,

• изучи ib различные классы упорядочений на дифференциальных мономах в зависимости от их согласованности с дифференцированиями, а также соотношения между этими классами, выяснить достоинс 1ва и недостахки таких классов (например, исследовав эффект сокращения иарших мономов в производных мноючлена),

• установить необходимые и досшточные условия конечности дифференциальных стандартных базисов при определенных упорядочениях,

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

• изучить поведение дифференциальных стандартных базисов и задачу о принадлежнос ги дифференциального многочлена идеалу при композиции mhoi очлеиов

Эти задачи успешно решены автром в данной pa6oie 1.3 Научная новизна

Научная новизна диссертции состоит в следующем

1 Рассмотрены допустимые упорядочения дифференциальных мономов без дополнительных предположений об их дифференциальных свойствах В частности, доказана полная упорядоченность множества дифференциальных мономов (в ошичие от [48, б, 36]) Исследован феномен сокращения мономов в производных многочлена Усыновлено, что при определенных упорядочениях могут сокращаться С1аршие мономы производных с'ла1аемых многочлена Предложен и реализован в еислеме компышерной алгебры Maple 10 алгоритм, сiроящий дифференциальным многочлен (если он су щес i вует), в ко юром сокращается заданная в общем виде последовательность мономов

2 Предложено описание упорядочений на дифференциальных мономах в терминах согласованною набора мономиальных матриц (или, чю эквивалентно, с помощью «бесконечных» матриц особого вида). Ранее некоторая довольно громоздкая классификация в терминах линейных форм (предложенная Ф Вайспфеннингом [47, 48]) существовала лишь для довольно узкого класса упорядочений, не охватывающего все требуемые случаи Выделены различные классы упорядочений в зависимоеiи от их связи с дифференцированиями Эти классы обобщают частые случаи лексико! рафического упорядочения (рассмотренного Оливье и Карра Ферро [6, 7, 36]) и упорядочения clegrevlex (неявно применяемою в pa6oie Леви [30])

3 Дано необходимое и достаточное условие сущее!вования конечною дифференциального сгандарi ного базиса заданно! о идеала при определенных классах упорядочений, что усиливает и распросфаняе! резуль-1аты Карра Ферро [7] для лексикографическо1 о упорядочения Приведены новые примеры конечных и параметрических дифференциальных ( ындартых базисов Предложен и реализован 1ак называемый «улучшенный процесс Оливье», заведомо остнавливаклцийся и возвращающий редуцированный дифференциальный стндартный базис идеала в случае его конечноеiи1 Получена связь между дифференциальными ыандаршыми базисами и наборами базисов Гребнера соотве!ствующих полиномиальных идеалов

4 Резулыаш X Хоша [19, 20] о поведении базисов Гребнера при композиции мноючленов обобщены на дифференциальный случай С помощью доказанных теорем о композиции и работы Леви [30] получено дост1 очное условие существования конечного дифференциальною стандартною базиса при /^-упорядочениях Сформулировано в виде ГШЮ1С5Ы анало1Ичное необходимое условие Исследована (совместно с М В Кондратьевой) задача принадлежности многочлена дифференциальному идеалу, порожденному композицией многочленов ее решение сведено к решению более просюй (с алгоритмической ючки зрения) задачи принадлежносш

Заключение

В работе рассматривались дифференциальные стандартные базисы идеалов (в смысле Дж Карра Ферро [б, 7] и Ф Оливье [36]) обыкновенного кольца дифференциальных многочленов oi одной независимой переменной при самых общих допустимых упорядочениях Доказано, чю каждое допустимое упорядочение на множестве мономов такою кольца задается каноническим согласованным набором мономиальных матриц, или, что эквивалентно, бесконечной матрицей определенного вида. Это обобщает хорошо известный результат о задании мономиальных упорядочений в случае обычных мономов от конечною числа переменных Были введены определенные классы упорядочений на дифференциальных мономах и установлены зависимости между ними Наиболее важные из них указаны на схеме в приложении А.1. Полученная теория была применена к доказательству критериев конечности дифференциальных стандартных базисов Для ^-лексикографических стандартных базисов этот критерий сводился к существованию квазилинейного мноючлена в идеале Было установлено, чю конечность ^-фиксированных базисов влечет конечност ь лексикографических базисов, что определяет особую роль чистого лексикографическото упорядочения На основе полученных критериев был разработан «улучшенный процесс Оливье», вычисляющий редуцированный (^-лексикографический дифференциальный стандартный базис идеала и всегда (в отличие от оригинально!о процесса Оливье) заканчивающий работу па идеалах с конечным таким базисом Он был реализован в системе компьютерной алгебры Maple С помощью компьютерных вычислений были получены новые примеры конечных и параметрических базисов

Отдельно были рассмотрены вопросы конечности дифференциальных стандартных базисов относительно /^-упорядочений, а также разработана теория поведения дифференциальных стандартных базисов при композиции мноючленов Среди допустимых композиций (при определенных упорядочениях) оказались лишь композиции с квазилинейными мноючленами С помощью этих результатов было установлено, что идеалы вида [/"], где / квазилинейный мноючлен, обладают конечным дифференциальным стандартным базисом из самою fn при любом согласованном с квазили-пеиностью /3-упорядочении Было также предложено в качестве гипотезы необходимое условие конечности дифференциальных стандартных базисов при согласованных с квазилинейное:ыо /^-упорядочениях В pa6oie было 1акже изучено явление сокращения заданной последовательное iи мономов в производных многочленов (в частности, сокращения старших мономов в производных при упорядочениях, не являющихся строю (^-устойчивыми)

Вопросы, рассмотренные в данной работе могут получить дальнейшее разви i ие в следующих направлениях1

• изучение «интегральных» дифференциальных идеалов; доказательство гипотезы 1 (или эквивалентной ей гипотезы 2) об интегральных свой-с твах дифференциальных идеалов [у11 ],

• доказательство гипотезы 3, дающей необходимое условие конечности дифференциальных стандартных базисов при согласованных с квазилинейное гыо /^-упорядочениях;

• построение1 идеала, не имеющего конечною дифференциального стандартною базиса ни при каком упорядочении,

• дальнейшее исследование классов допустимых упорядочений на дифференциальных мономах, исследование аналогов веера Гребнера в дифференциальном случае, построение аналога универсального базиса Гребнера [2],

• исследование идеалов, порожденных одним дифференциальным многочленом малого порядка, установление связи между радикальностью такого идеала и конечностью его дифференциального стандартного базиса [26, 65], распространение методов Кол чипа [26] изучения экспонент таких идеалов на случай мноючленов большею порядка

• построение (если эю возможно) алгоритма проверки существования в идеале квазилинейного (линейного) мноючлена;

• обобщение всех полученных результатов на случай нескольких дифференцировании и нескольких независимых переменных,

• разработка теории рекурсивных дифференциальных стандартных базисов

Все поставленные задачи гесно связаны (о следующей глобальной задачей сцщсствупп ли алгоритм проверки принадлежности дифференциального многочлена конечно пороподенному дифференциальному идеалу в кольче duefxfiepe нциальныг многочленов Т{у}'1' Как было сказано в начале рабо-I ы, л а задача положи i ел ьио решена лишь в некоюрых частных (но важных) случаях Данная работа позволяет расширить круг идеалов, для которых известно алторитмическое решение задачи принадлежности

1. Becker Г and Wc ispfennmg W , Groebner Basts A Computational Approach to Commutative Algebra, Graduate IYxtb 111 Mathematics, Springe r-Verlag, New York, 1993

2. Boulier F , Etude e1 implantation dc qutlques algorightrnes en algebre differentielle, These de l'Umvcrsite des Sciencсь et Technologies de Lille, 1994

3. Boulicr F , lazard D , Olhvier F , Pctitot M , Representation for the Radical of a Finitely Generated Differential Ideal, m Proceedings of 1995 International Symposium on Symbolic and Mgebraic Computation, 158 166, ACM Press, 1995

4. Buchberger В , Grobner Bases an Algorithmic Method m Polynomial Ideal Iheory, m Multidimensional S> stems Theory, ed by Bose \т К , D Reidel Publishing Company, Dordrccht, 184-232

5. Carr& Ferro G , Groebner Bases and Differential Algebra, Lecture Notes in Computer Science, vol 356, 129-140, 1989

6. Carrfi Ferro G , Differential Grobntr Bases in One Variable and in the Partial Case, Math Comput Modelling, Pergamon Press, vol 25, 1-10, 1997

7. Chou S-C , Mecheinual Geometry Theorem Proving, D Reidel Publishing Company, Dordrccht, 1988

8. Сох D , Little J , O'Shea D , Using Algebraie Geometry, Springer-Verlag, New-York Berlin Heidelberg, 1998

9. Faugere J -C A New Efficient Algorithm for РУотрикпд Grobner Bases 1999

10. Faugere I С A New Efficient Algorithm for Computing Grobner Bases withemt Reduction to Zero (F*,), 1999

11. Gallo G , Mishra В , Efficient Algorithms and Bounds for Wu-Ritt Characteristic Sets, Effective Methods in Algebraic Geometry, (Edited by F Mora and С Traverso), pp 119 142, Progress m Mathematics, vol 94, Birkhauscr Boston, Ine , 1991

12. Gallo G , Mishra В , Olhvier F , Some Construe tions in Rings of Differential Polyrwmials, Lecture Notes in Computer Science, vol 539, 171-182, 1991

13. Golubitsky О , Differential Groebner Walk, m Proceedingb of International Workshop on Computer Algebra and its Applications to Physics, Dubna, Russia, 114-126, 2001

14. Gutierrez J , anil Rubio San Miguel R , Reduces Grobner Bases Under Composition Journal of Symbolic Computation, vol 26, 433 444, 1998

15. Hong H , Groebner Basis Under Composition I, lhe Journal of Symbolic Computation, 643-663, 25 (5), 1998

16. Hong II , Groebner Basis Undtr Composition II, in Proceedings of ISSAC-1996, 79 85, 1996

17. Hong II and Wcispfcnning V , Algorithmic Theory of Admissible Term Orders, preprint, 1999 http //www4 ncsu ulu 8030/~hong/papers/Hong99c dvi

18. Hubert E , Essential Components of an Algebraic Differential Equation, Journal of Symbolic Computation, vol 28 (4 5), 657-680, 1999

19. Hubert E, Factorization-free Decomposition Algorithm in Differential Algebra, Journal of Symbolic Computation, vol 29,641 662,2000

20. Hubert E , Notes on triangular sets and triangulation-deeomposition algorithms I Polynomial Systems, Symbolic and Numerical Scientific Computing 2001, 1 40, 2003

21. Hubert E , Notes on triangular sets and triangulatiori-decomposition algorithms II Differential Systems, Symbolic and Numerical Scientific Computing 2001, 40-87, 2003

22. Kolchm E R On the exponents of differential ideals, Annalb of Mathematics, 42 740 777, 1941

23. Kolchm E R , Differential Algebra and Algebraic Groups, Academic Press, 1973

24. Kondratieva M V , Levin А В , Mikhalev A V , Pankratiev E V , Differential and Difference Dimension Polynomials, Kluwer Academic Publisher, 1999

25. Kredel H , Wci&pfenning V , Computing Dimension and Independent Set for Polynomial Ideals, Journal of Symbolic Computation, vol 6, 231 247, 1988

26. Levi H , On the Structure of Differential Polynomials and on Their Theory of Ideals, Trans AMS, vol 51, 532 568, 1942

27. Mansfield E Differential Grobner Bases, PhD Thesis, Urnv of Sydney, 1991

28. Mansfield E , Fat knell E D Differential Grobner Bases, preprint, 1992

29. Mead D G , A Necessary and Sufficient Condition for Membership m uv], Proc AMS, vol 17, 470-473, 1966

30. Mead D G , Newton M E , Syzygies m \xfz\, Proc AMS, vol 43 (2), 301 305, 1974

31. Olhvier F , Le probleme de I'ldentifiabilite structurelle globule, Doctoral Dissertation, Pans, 1990

32. Olliuer F , Standard Bases of Differential Ideals, Lecture Notts in Computer Science, 304-321, 508, 1990

33. O'Kccfe 1ч В , A Property of the Differential Ideal yr'}: Trans AMS, vol 94, 483-497, 1960

34. Hitt J Г , Differential Algebra, volume XXXIII of Colloquium Publications New York, American Mathematical Society, 1950

35. Robbiano L, Term Ordcrings on the Polynomial Ring, in Proceedings of EUROCAL 85, Springer Lccture Notts in Computer Science 204, 513-517, 1985

36. Robbiano L , On the Theory of Graded Structures, The Journal of Symbolic Computation, 2, 139-170, 1986

37. Rust С , Reid G J , Rankings of Partial Derivatives, in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 9-16, ACM Press, New York, 1997

38. Rust С , Rankings of Derivatives for Elimination Algorithms and Formal Solvability of Analytic Partial Differential Equations, Ph D dissertation, Chicago, Illinois, 1998

39. Sit W Y , The Ritt-Kolchin Theory for Differential Polynomials, Differential Algebra and Related Topics, Proceedings of the International Workshop, NJSU, 2-3 November 2000, edited by Li Guo, William F Keigher, Phyllis ] Cassidy, William Y Sit, 20

40. Trevisan G , Classificazione dei semphci ordmamenti di un gruppo libero commutative con N generators Rend Sem Mat Padova, 22, 143-156, 1953

41. Wcispfelining V , Admissible Orders and Linear Forms, in ACM SIGSAM Bulletin, 21 / 2, 16 18, 1987

42. Weispfenmng V , Differential Term-Orders, m Proceedings of the 1993 International Symposium on Sjmbohc and Algebraic Computation, 245-253, ACM press, Kiev, 1993

43. Weispfenning V , Grobner Bases for Binomials with Parametric Exponents, in Proceedings of the 7th International Workshop on Computer Algebra in Scientific Computing (CASC-2004), July 12 19, 2004, St Petersburg, Russia, pp 467 477 (2004)

44. Wu Wen Tsun, On 'Good" Bases of Algebraico-Differential Ideals, Differential Equations with Symbolic Computation, 343 350, 2005

45. Арланцев И В , Базисы Гребнера и системы алгебраических уравнений, М , МЦНМО, 2003

46. Вереща! ин II К , Шень А X , Начала теории множеств, М , МЦНМО, 1999

47. Кап 1анский И , Введение в дифференциальную алгебру, 1957

48. Кондратьева М В , Примеры вычисления обязующих дифференциального идеала по характеристическому множеству, Программирование, Л"° 2, 34-37, 2002

49. Латышев В Н , Комбинаторная теория колец Стандартные базисы, Ичда1ельспю Московского >ниверситета, 1988

50. Панкратьев Е В , Стандартные базисы в дифференциальной алгебре, Вестник Мое коне кого >нивсрситс га, Сер 1, Математика, механика, 3, 48-56, 2003

51. Трушин Д В , Идеал cenajxmm в кольце дифхреренциальных многочленов, принято к печати в журнале «Фундаментальная и прикладная ма!ема1ика», 2006

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

53. Зобнин А О стандартных базисах в кольце дифференциальны г многочленов Фундамсн-ia п,пая и ирик ыдная математика, том 9, пып 3, стр 89 102 (2003)

54. Перевод Zohinti AI On Standard Bases in Rings of Differential Polynomials Journal of Mathematical Sciences, vol 135, no 5 (2006)

55. Zobniii \ Essential Properties of Admissible Orderings and Rankings Contributions to Central Algebra 14, pp 205-221 (2004)

56. GO. Зобнин Л Обобщенная редукция в кольца дифференциальных многочленов Программирование, .V" 30 (2), с 1 р 42-50 (2004)

57. Перевод Zobnin A Generalized Reduction in Rings of Differential Polynomials Programming and Computer Software, vol 30, no 2, pp 88-94 (2004)

58. Zobnin A On Testing the Membership to Differential Ideals In Proceedings of the 7th International Workshop on Computer Algebra m Scientific Computing (CASC-2004), July 12 19, 2004, St Petersburg, Russia, pp 485-496 (2004)

59. Zobnin A Some Results on Differential Grobner Bases In Proceedings of A3L-2005 (Conference in Honor of the 60th Birthday of Volker Weispfenning), April 3-6, Passau, Germany, pp 309-314 (2005)

60. Zobnin A Admissible Oidenngs and Fimteniss Criteria for Differential Standard Bases In Proceedings of International Symposium oil Symbolic and Algebraic Computation (ISSAC-2005), July 24-27, Beijing, China, pp 365-372 (2005)

61. Кондратьева M В , Панкратьев E В , Зобнин А И и Трушин Д В Вопросы конечности дифференциальных стандартных базисов Материапы IX международной конференции «Интеллектуальные системы и компьютерные науки», том 1, часть 2, 141-144 (2006)

62. Зобнин А И Поведение дифференциальных стандартных базисов при композиции «Фундаментальная и прикладная математика», том 13, выпуск 1, стр 109 134 (2007)