Символьные алгоритмы и программы вычисления булевых базисов Грёбнера тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Зинин, Михаил Владимирович

• Зинин, Михаил Владимирович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Зинин, Михаил Владимирович

Введение

Глава 1. Булевы базисы Грёбнера и инволютивные базисы

1.1. Основные обозначения

1.2. Булевы функции, многочлены и кольцо.

1.3. Булевы базисы Грёбнера.

1.4. Булевы инволютивные базисы.

Глава 2. Алгоритмы вычисления булевых базисов.

2.1. Некоторые существующие алгоритмы построения базисов Грёбнера

2.1.1. Алгоритм Бухбергера

2.1.2. Инволютивный алгоритм.

2.1.3. Вычисление булевых базисов в кольце

2.2. Инволютивный алгоритм на основе деления Жане.

2.2.1. Подробное описание алгоритма.

2.3. Инволютивный алгоритм на основе деления Поммаре

2.3.1. Вычисление базиса Поммаре в кольце ¥2[Х].

2.3.2. Вычисление базиса Поммаре в кольце В [X].

2.3.3. Подробное описание алгоритма.

Глава 3. Программная реализация.

3.1. Реализация утилит ВЛВ и ВРВ на языке программирования

Си++.

3.1.1. Преимущества и недостатки векторизации в представлении мономов

3.1.2. Представление мономов односвязным списком

3.1.3. Представление многочленов.

3.1.4. Выбор мономиального упорядочения.

3.2. Реализация пакета BIBasis в системе Macaulay

3.2.1. Реализация и представление данных.

3.2.2. Пользовательский интерфейс.

3.2.3. Примеры использования.

3.3. Реализация пакета BIBasis в системе REDUCE.

3.3.1. Реализация и представление данных.

3.3.2. Пользовательский интерфейс.

3.3.3. Примеры использования.

Глава 4. Результаты компьютерных экспериментов.

4.1. Выбор тестовых примеров.

4.2. Сравнение делений Жане и Поммаре.

4.3. Сравнение с пакетами Singular и PolyBoRi.

4.4. Система компьютерной алгебры Macaulay2, сравнение пакета BIBasis и встроенного пакета gb.

4.5. Система компьютерной алгебры REDUCE, сравнение пакетов BIBasis и Groebner.

4.6. Выводы.

Введение диссертации (часть автореферата) на тему «Символьные алгоритмы и программы вычисления булевых базисов Грёбнера»

Объект исследования и актуальность работы. Базис Грёбне-ра представляет собой каноническую форму системы алгебраических [1], дифференциальных [2, 3] или разностных [4] многочленов многих переменных. Приведение систем таких многочленов к данной канонической форме является наиболее универсальным алгоритмическим подходом к их исследованию и решению.

Так, построение базиса Грёбнера для системы алгебраических уравнений полиномиального типа позволяет установить её совместность (т.е. наличие общих корней у многочленов системы), определить число (а в случае бесконечного числа — размерность пространства) решений, привести исходную систему к треугольному виду, либо исключить часть переменных. В целом метод базисов Грёбнера является обобщением метода Гаусса на случай нелинейных систем.

Алгоритмически задача нахождения базиса Грёбнера для заданной системы многочленов в коммутативной алгебре была решена около полувека назад Б.Бухбергером [1], а соответствующий алгоритм [5] получил имя автора. С тех пор усилиями многих исследователей базисы Грёбнера нашли плодотворное применение в различных областях математики и естественных наук и в настоящее время обладают обширным числом практических приложений [6].

Расширение области применения базисов Грёбнера не обошло стороной и специфический случай систем булевых многочленов. Впервые алгоритм вычисления булевых базисов Грёбнера был представлен в [7]. Теоретическим фундаментом идеи использования базисов Грёбнера в булевых кольцах послужила весьма развитая к тому времени теория булевых функций.

Напомним, что п—местной булевой функцией называется отображение 0,1}п в { 0,1} [8]. Для булевых функций определено понятие их суперпозиции, и, как следствие, для любого множества булевых функций может быть получено его замыкание — как множество всех функций, получаемых с помощью суперпозиции из функций исходного множества. В таком случае говорят, что множество ф порождает замкнутый класс булевых функций Я: [ф] = Я (замкнутый, т.к. очевидно, что [[Я]} = [Л]). Если [Я] совпадает со множеством всех булевых функций, то порождающее множество ф называют полным. Базисом замкнутого класса Я в теории булевых функций называют такое множество Скоторое порождает класс Я, но при этом ни одно несобственное подмножество ф этого класса не порождает.

Известно, что множество булевых функций {1,х + у,ху} полно [8] (здесь 1 — функция-константа единица, х + у — сложение по модулю 2, ху — конъюнкция). Причем функции х + у и ху являются соответственно сложением и умножением в поле Галуа ¥2 = {0,1}. Поэтому, пользуясь коммутативностью сложения и умножения, дистрибутивностью умножения относительно сложения и соотношениями ж+я = О, х-х = х, всякую функцию из замыкания множества {1,х + у, ху} (т.е. любую булеву функцию) можно представить в виде многочлена Жегалкина [8]: где а, £ В данной работе мы будем называть многочлен Жегалкина булевым многочленом. Все такие многочлены от заданного конечного набора переменных {х\,.,хп} образуют кольцо, которое мы будем называть булевым. Это кольцо является эквивалентом булевой алгебры [9]. Более того, каждая булева функция представима булевым многочленом единственным образом [8]. Как и в случае булевых функций, множество булевых многочленов порождает идеал в булевом кольце, причем булево кольцо является кольцом главных идеалов, т.е. каждый идеал кольца по рождается его единственным элементом.

Базисы Грёбнера в целом, как уже было сказано, и булевы в частности, оказываются весьма полезными в случаях, когда решение некоторой задачи связано с исследованием и/или решением соответствующей полиномиальной системы [10-12]. В случае булева кольца наиболее распространенными задачами такого рода являются задачи криптоанализа и булевой выполнимости. Например, одним из первых ярких применений метода булевых базисов Грёбнера стало решение сложной [13] проблемы — криптосистемы на скрытых отображениях полей (Hidden Fields Equations) в криптографии с открытым ключом. Эта задача описывается системой квадратичных булевых многочленов от 80 переменных, и впервые ее решение было получено именно путем вычисления булева базиса Грёбнера с помощью алгоритма F5, позднее — с помощью алгоритма F4 [14, 15].

Задача булевой выполнимости SAT (Boolean Satisfiability) — очень распространенная и, в общем случае, MV—полная [16] задача, которая возникает, в частности, при проверке корректности работы оборудования и программ, в робототехнике, при создании экспертных систем и т.п. Для решения этой задачи разработан ряд успешных и широко применяемых специализированных алгоритмов. В настоящее время уже известен ряд примеров [17] успешного применения техники булевых базисов Грёбнера к решению задачи булевой выполнимости. Через 12 лет после теоретического обоснования [18] применимости таких базисов для решения задач SAT был создан программный пакет PolyBoRi [19], использующий метод базисов Грёбнера и способный конкурировать с лучшими современными программами решения задач булевой выполнимости (SAT-solvers).

Приведем простой пример задачи булевой выполнимости, иллюстрирующий применение метода базисов Грёбнера для её решения, т.е. для ответа на вопрос: существует ли для заданной булевой функции такой набор значений переменных, на котором функция принимает значение 1 (истина)? В терминах базисов Грёбнера данный вопрос формулируется следующим образом: состоит ли соответствующий базис Грёбнера из одного многочлена, который, в свою очередь, является единичным булевым мономом {1}) или нет? В последнем случае рассматриваемая задача является выполнимой.

Пусть булева функция, заданная в своей конъюнктивой нормальной форме, имеет вид: ж, у, £) = {х V у V г) Л (х V у) Л (у V г) Л (г V х) Л (х V у V г) 11 А к А /з Л /4 Л /б

Приведем функцию к полиномиальному виду, используя следующие формулы: х Л у —> ху, х V у —> ху + х + у, х —> х + 1

Тогда булева выполнимость рассматриваемой задачи сводится к существованию решения в F2 у системы булевых многочленов / х = хуг + ху + хг + уг + х + у + г + 1 /2 = ху + у < /з = 2/2 + г ¡¿ = хг + х к = ХУ*

Вычисление базиса Грёбнера для данной системы многочленов показывает, что этот базис равен {1}, т.е. полиномиальная система не имеет решений (несовместна), и задача невыполнима.

Ещё одним интересным применением булевых базисов Грёбнера может стать моделирование квантовых вычислений, т.е. построение унитарной матрицы квантовой цепи на классическом компьютере. Как показано в [20], для квантовой цепи с помощью вентилей Тоффоли и Адамара (они образуют универсальный базис вентилей) её цепная матрица однозначно определяется числом общих корней (когда все переменные принимают значения в Рг) системы булевых многочленов. В работе [21] описан пакет для системы Ма-^ета-Ыса [22], позволяющий пользователю по введенной квантовой цепи строить её цепную унитарную матрицу стандартными методами линейной алгебры, а также автоматически создавать систему определяющих её булевых многочленов. На практике, в силу ограниченности памяти компьютера, методами линейной алгебры удается промоделировать лишь 20-25 кубитные схемы. И хотя задача построения базисов Грёбнера в булевых кольцах имеет экспоненциальную сложность [23], уже сейчас эта задача решается для некоторых систем многочленов от 100 и более переменных [17], что дает реальную надежду на то, что базисы Грёбнера, по крайне мере в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.

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

Таким образом, можно утверждать, что в настоящее время существует практическая потребность в быстрых и высокоэффективных алгоритмах для вычисления булевых базисов Грёбнера и их реализациях, что заставляет исследователей искать и находить новые, более эффективные алгоритмы для их построения. К таковым можно отнести уже упоминавшиеся алгоритмы F4 и ^ французского математика Фожера, целый ряд модификаций алгоритма например, алгоритмы С2У и СУ\¥ [25] — результат работы китайских и американских исследователей, а также инволютивный алгоритм [26, 27] Блинкова и Гердта. Булевой версии последнего и посвящена данная работа.

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

Для достижения поставленной цели решаются следующие основные задачи:

• Исследование современных алгоритмов построения базисов Грёбнера в полиномиальных кольцах и условий их применимости для вычисления булевых базисов Грёбнера.

• Разработка специализированного алгоритма, способного строить булев базис Грёбнера путем вычислений непосредственно в булевом кольце.

• Реализация разработанного алгоритма на языке С++ и ее оптимизация на основе эмпирических данных, полученных с помощью компьютерных экспериментов.

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

Научная новизна. В диссертационной работе получен ряд результатов, обладающих научной новизной:

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

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

• В системы компьютерной алгебры с открытым кодом REDUCE (версия 3.8) и Macaulay2 (версия 1.4.1) встроены новые пакеты, которые предназначены для построения булевых базисов Грёбнера и значительно превосходят по своей вычислительной эффективности имевшиеся в этих системах возможности для указанного построения.

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

Реализация алгоритма в виде пакета BIBasis встроена в открытые системы компьютерной алгебры Macaulay2 и REDUCE. Это существенно расширяет применимость указанных систем для решения задач, сводящихся к булевой логике. При этом Macaulay2 является одной из наиболее широко используемых программных систем специального назначения, ориентированных на задачи вычислительной коммутативной алгебры и алгебраической геометрии, a REDUCE является системой компьютерной алгебры общематематического назначения и находит применение в различных областях науки и техники.

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

1. Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце. В результате показано, что инволютивный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем F2, а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.

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

3. Разработанный булев инволютивный алгоритм на основе деления Поммаре, а также алгоритм на основе деления Жане реализованы на языке программирования С++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Поммаре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Macaulay2 и REDUCE. Пакет доступен под лицензией GPL v2.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• Международная конференция по компьютерной алгебре и дифференциальным уравнениям. Доклад «О вычислении базисов Грёбнера над i<2», Финляндия, Турку, 20 — 23 февраля 2007 г.

• 11-ое международное совещание по компьютерной алгебре. Доклад «Инволютивный метод вычисления базисов Грёбнера над F2», Россия, Дубна, 24 - 25 мая 2007 г.

• 4-ое международное совещание «Квантовая физика и информация». Доклад «Алгоритмический подход к решению полиномиальных уравнений, описывающих квантовые схемы», Россия, Дубна, 15 — 19 октября 2007 г.

• 12-ое международное совещание по компьютерной алгебре. Доклад «О роли инволютивных критериев при вычислении булевых базисов Грёбнера», Россия, Дубна, 14 — 15 мая 2008 г.

• Международная конференция «Математическое моделирование и вычислительная физика», ММСР 2009. Доклад «О вычислении булевых инволютивных базисов», Россия, Дубна, 7—11 июля 2009 г.

• Международная конференция «Полиномиальная компьютерная алгебра», РСА 2010. Доклад «Булевы инволютивные базисы и решение задач булевой выполнимости», Россия, Санкт-Петербург, 2 — 7 апреля 2010 г.

• 14-ое международное совещание по компьютерной алгебре. Доклад «Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Масаи1ау2», Россия, Дубна, 2 — 3 июня 2011 г.

Публикации. По материалам диссертации опубликовано 8 печатных работ: 5 статей в рецензируемых журналах, рекомендованных ВАК [28-32], и 3 статьи в сборниках трудов конференций [33-35].

Личный вклад автора. Основные положения и выводы диссертации являются результатом самостоятельных исследований автора, выполненных под руководством д.ф.-м.н., профессора В.П. Гердта. Постановка и формализация задачи, разработка математических моделей и алгоритмов выполнены соискателем совместно с научным руководителем и соавторами. Практическая реализация, исследование форм представления данных, численные расчеты и анализ результатов проводились соискателем самостоятельно. Также соискателем самостоятельно создан и встроен в системы компьютерной алгебры REDUCE и Macaulay2 специализированный пакет для построения булевых базисов Грёбнера, и опубликована работа [32], описывающая данный пакет.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации составляет 114 страниц, включая 34 рисунка и 4 таблицы. Список литературы содержит 63 наименования.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Зинин, Михаил Владимирович

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

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

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

3. Разработанный булев инволютивный алгоритм на основе деления Поммаре, а также алгоритм на основе деления Жане реализованы на языке программирования С++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Поммаре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Масаи1ау2 и REDUCE. Пакет доступен под лицензией GPL v2.

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

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

Мне приятно поблагодарить Юрия Анатольевича Блинкова за полезные обсуждения, замечания, критику и помощь в создании пакета BiBasis для системы REDUCE

Я также очень признателен Винфриду Нойну (Winfried Neun) и Дэниэ-лу Грейсону (Daniel Grayson) за согласие и помощь в размещении исходных кодов пакета BiBasis в разрабатываемых ветках систем компьютерной алгебры REDUCE и Macaulay2 соответственно.

И отдельную благодарность я выражаю своей жене — Зининой Александре Александровне, и родителям — Зинину Владимиру Михайловичу и Зининой Татьяне Ивановне за терпение и моральную поддержку, позволившие мне довести данную работу до конца.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Зинин, Михаил Владимирович, 2013 год

1. Kandri-Rody A., Weispfenning V. Non-commutative Gröbner bases in algebras of solvable type // Journal of Symbolic Computation. 1990. Vol. 9. Pp. 1-26.

2. Gerdt V. P. On Computation of Gröbner Bases for Linear Difference Systems. // Nuclear Instruments and Methods in Physics Research. 2006. Vol. 559(1). Pp. 211 214. URL: arXiv.org:math-ph/0509050.

3. Brickenstein M. Boolean Gröbner bases — Theory, Algorithms and Applications: Ph. D. thesis / Technischen Universität Kaiserslautern. 2010.

4. Sakai K., Sato Y. Boolean Gröbner Bases, 1988.

5. Марченков С. С. Замкнутые классы булевых функций. Москва: Физматлит, 2000. ISBN: 5-9221-0066-1.

6. Hsiang J., Huang G. Some Fundamental Properties of Boolean Ring Normal Forms // DIMACS series on Discrete Mathematics and Computer Science: The Satisfiability Problem. 1997. Vol. 35. Pp. 587-602.

7. Sato Y., Inoue S., Suzuki A. et al. Boolean Grôbner bases // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 622-632.

8. Kalorkoti K. Model checking in the modal /г-calculus and generic solutions // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 584-594.

9. Bernasconi A., Codenotti В., Crespi V., Resta G. Computing Grôbner Bases in the Boolean Setting with Applications to Counting.

10. Bardet M., Faugère J.-С., Salvy В., Spaenlehauer P.-J. On the Complexity of Solving Quadratic Boolean Systems. 2011. URL: arXiv.org: 1112. 6263vl.

11. Faugère J.-C. A new efficient algorithm for computing Grôbner bases (F4) // Journal of Pure and Applied Algebra. 1999. Vol. 139, no. 1-3. Pp. 61-88. URL: http://www-salsa.lip6.fr/~jcf/Papers/F99a.pdf.

12. Garey M. R., Johnson D. S. Computers and Intractability: a Guide to the Theory of HV—completeness. New York: Freeman, 1978.

13. Clegg M., Edmonds J., Impagliazzo R. Using the Grobner Basis algorithm to find proofs of unsatisfiability // Proc. 28th Annual ACM Symposium on Theory of Computing. 1996. Pp. 174-183.

14. Dawson C. M., Haselgrove H. L., Hines A. P. et al. Quantum computing and polynomial equations over the finite field // Quantum Information and Computation. 2005. Vol. 5, no. 2. Pp. 102-112. URL: arXiv.org: quant-ph/0408129vl.

15. Mathematica 6.0. Champaign, Illinois, USA: Wolfram Research, Inc., 2007. URL: http://www.wolfram.com/.

16. Arithmetic of Finite Fields. Vol. 5130 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008.

17. Volny IV F. New Algorithms for Computing Grobner Bases: Ph. D. thesis / Clemson University. 2011. URL: http://etd.lib.clemson.edu/ documents/1306872881/Volnyclemson0050D11180.pdf.

18. Gerdt V. P., Blinkov Y. A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation. 1998. Vol. 45. Pp. 519-542. URL: arXiv.org:math.AC/9912027.

19. Гердт В. П., Зинин М. В. Инволютивный метод вычисления базисов Грёбнера над F2 // Программирование. 2008. Т. 34, № 4. С. 191-203.

20. Гердт В. П., Зинин М. В. О роли инволютивных критериев при вычислении булевых базисов Грёбнера // Программирование. 2009. Т. 35, № 2. С. 90-97.

21. Gerdt V. P., Zinin М. V. An algorithmic approach to solving polynomial equations associated with quantum circuits // Physics of Particles and Nuclei Letters. 2009. Vol. 6, no. 7. Pp. 521-525.

22. Гердт В. П., Зинин М. В., Блинков Ю. А. О вычислении булевых инво-лютивных базисов // Программирование. 2010. Т. 36, № 2. С. 117-125.

23. Зинин М. В. Пакет BiBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulay2 // Программирование. 2012. Т. 38, № 2. С. 55-67.

24. Gerdt V. Р., Zinin М. V. Gröbner bases over F2 // Computer Algebra and Differential Equations. Vol. 67. 2007. Pp. 59-68.

25. Gerdt V., Zinin M., Blinkov Y. On computation of Boolean involutive bases // Proceedings of International Conference Polynomial Computer Algebra. 2009. Pp. 17-24.

26. Gerdt V. P., Zinin M. V. A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings // Proceedings of ISSAC 2008. ISSAC'08. New York: ACM Press, 2008. Pp. 95-102.

27. Кокс Д., Литтл Д., О'Ши Д. Идеалы, многообразия и алгоритмы. Москва: Мир, 2000. ISBN: 5-03-003320-3.

28. Жарков А. Ю., Блинков Ю. А. Инволютивные системы алгебраических уравнений // Программирование. 1994. Pp. 53-56.

29. Faugere J.-C. FGb. 2012. URL: http://www-polsys.lip6.fr/~jcf/ Software/FGb/index.html.

30. Apel J., Hemmecke R. Detecting Unnecessary Reductions in an Involu-tive Basis Computation: Tech. rep.: RISC, 2002. URL: ftp://ftp.risc. uni-linz.ac.at/pub/techreports/2002/02-22.ps.g.

31. Geddes K. 0., Czapor S. R., Labahn G. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.

32. Gerdt V. P., Blinkov Y. A., Yanovich D. A. Computation of Janet Bases. I.Monomial Bases // Computer Algebra in Scientific Computing / CASC 2001. Berlin: Springer-Verlag, 2001. 233-247 pp. URL: http://invo. jinr.ru/Papers/casc01-l.ps.gz.

33. Gerdt V. P., Blinkov Y. A., Yanovich D. A. Computation of Janet Bases. II. Polynomial bases // Computer Algebra in Scientific Computing / CASC 2001. Berlin: Springer-Verlag, 2001. 249-263 pp. URL: http://invo. jinr.ru/Papers/casc01-2.ps.gz.

34. Apel J. A Gröbner Approach to Involutive Bases // Journal of Symbolic Computation. 1995. Vol. 19. Pp. 441-458. URL: http://www.informatik. uni-leipzig.de/~apel/publications/jscl995.ps.

35. Becker T., Weispfenning V., Kredel H. Gröbner bases: A computational approach to commutative algebra. New York: Springer-Verlag, 1993.

36. Engel K. Sperner theory. Cambridge University Press, 1997. 215 pp.

37. Sato Y. Parallel computation of boolean Gröbner bases // ACM SIGSAM Bulletin. 2000. Vol. 34. Pp. 27 28.

38. Gerdt V., Yanovich D. Parallel Computation of Janet and Gröbner bases over rational numbers // Programming and Computer Software. 2005. Vol. 31, no. 2. Pp. 73 80.

39. Zinin M. Utility for computing boolean Groebner and Pommaret bases. 2011. URL: http://bpb.googlecode.com.

40. Grayson D. R., Stillman M. E. Macaulay2, a software system for research in algebraic geometry. 2011. URL: http://www.math.uiuc.edu/ Macaulay2/.

41. Eisenbud D., Grayson D. R., Stillman M. E., Sturmfels B. Computations in algebraic geometry with Macaulay 2. Springer-Verlag, 2001. Vol. 8 of Algorithms and Computations in Mathematics. URL: http://www.math. uiuc.edu/Macaulay2/Book.

42. Исходный код системы компьютерной алгебры Macaulay2. 2011. URL: svn://svn.macaulay2.com/Macaulay2/trunk/M2/.

43. Hearn A. C. REDUCE, a portable general-purpose computer algebra system. 2009. URL: http://www.reduce-algebra.com/.

44. Neun W. Portable Standard Lisp. 1999. URL: http://www2.zib.de/ Symbolik/reduce/.

45. Ltd. C. Codemist Standard LISP. 2002. URL: http://www.codemist. co.uk.

46. Исходный код системы компьютерной алгебры REDUCE. 2011. URL: https://reduce-algebra.svn.sourceforge.net/svnroot/ reduce-algebra/trunk/.

47. Decker W., Greuel G.-M., Pfister G., Schonemann H. Singular 3-1-3 A computer algebra system for polynomial computations. 2011. URL: http: //www.singular.uni-kl.de.

48. Bini D., Mourrain B. Polynomial test suite. 2006. URL: http://www-sop. inria.fr/saga/POL.

49. Verscheide J. The database of polynomial systems. 2011. URL: http: //www.math.ui c.edu/~jan/demo.html.

50. Kornyak V. V. On Compatibility of Discrete Relations // CASC-2005 proceedings. LNCS 3718. Springer-Verlag, 2005. 272-284 pp. URL: arXiv.org:math-ph/0504048.

51. Hoos H. H., Stützle T. SATLIB: An Online Resource for Research on SAT // SAT 2000, Ed. by I. P. Gent, H. V. Maaren, T. Walsh. IOS Press, 2000. 283 292 pp.

52. Brickenstein M., Dreyer A. PolyBoRi: A Gröbner Basis Framework for Boolean Polynomials // Reports of Fraunhofer ITWM. Vol. 122. 2007. URL:http://www.itwm.fraunhofer.de/fileadmin/ITWM-Media/ Zentral/Pdf/BerichteITWM/2007/bericht122.pdf.

53. Hinkelmann F., Arnold E. Fast Gröbner Basis Computation for Boolean Polynomials. 2010. URL: arXiv.org: 1010.2669vl.