Методы искусственных ограничений и полилинейных форм для решения некоторых метрических и алгоритмических задач в теории дискретных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО 'ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА Факультет вычислительной математики и кибернетики

Р Г Б СЛ

1 (1 Л!.? Г* ' На правах рукописи

АЛЕКСЕЕВ Валерий Борисович

1ЕТ0ДЫ ИСКУССТВЕННЫХ ОГРАНИЧЕНИЙ И ПОЛИЛИНЕЙНЫХ ФОРМ ДЛЯ РЕШЕНИЯ ЕКОТОРЫХ МЕТРИЧЕСКИХ И АЛГОРИТМИЧЕСКИХ ЗАДАЧ В ТЕОРИИ ДИСКРЕТНЫХ

ФУНКЦИЙ

Специальность 01.01.09 - математическая кибернетика

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

Москва-1995

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

Официальные оппоненты: доктор физико-математических наук

профессор М.М.Глухов, доктор физико-математических наук профессор Н.К.Косовский, доктор физико-математических наук профессор Р. И.Подловченко

Ведущая организация - Нижегородский государственный

университет им. Н.И.Лобачевского

Защита диссертации состоится, оИ в и час. оо мин. на заседании диссертационного Совета факультета вычислительной математики и кибернетики МГУ по адресу: 119899, ГСП, Воробьевы горы, МГУ, факультет ВМиК^

уз-

С диссертацией можно ознакомиться в библиотеке факультета. Автореферат разослан

_1995 Г.

Ученый секретарь диссертационного Совета профессор

Н.П.Трифонов

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

Акт^альность_темц_исслеаований. Теория дискретных функций (таких, например, как k-значные или частичные к-значные функции) является важным разделом современной математики, который тесно связан с такими разделами, как алгебра, математическая логика, теория чисел. Большой интерес к теории дискретных функций связан также с изучением процессов обработки информации, с созданием различных вычислительных и управляющих систем.

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

Среди характеристик любого математического объекта важное значение имеют его количественные характеристики. Для классов дискретных функций одной из наиболее важных таких характеристик является число ip(п) функций в' классе, зависящих от п фиксированных переменных. Это число pin) конечно для любого класса k-значных или частичных к-значных функций. Кроме непосредственной количественной характеризации данного класса функция р(п) характеризует сложность алгоритмов, связанных с перебором функций данного класса, минимальную длину кодов для кодирования всех функций данного класса, зависящих от п переменных. Как показал О.Б. Лупанов, наибольшая сложность схем, реализующих булевы функции из некоторого класса зл, связана с асимптотикой логарифма числа функций в зл, зависящих от п переменных. Исследования показывают, что не только установление точной формулы, но даже получение достаточно хороших оценок для ¥> (п), в большинстве случаев представляет собой трудную задачу.

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

оказалась очень трудной. Эта задача была поставлена еще Дедекиндом в 1897 г. как проблема вычисления числа свободных дистрибутивных структур с п образующими. В 1963г. Коробков установил порядок при п -> « для log2iMn), где 0(п) - число монотонных булевых функций. В 1966 г. Ж. Ансель улучшил оценки для log20(n), но не смог получить асимптотику для log^tn). В 1969 г. Д.Клейтмен получил асимптотику для log2tf/{n). И только в 1977 г. Коршунов Л.Д. установил асимптотику для iMn). Позднее более простое доказательство асимптотической формулы для <J>(n) получил Сапоженко A.A.

Другим примером , может служить проблема оценки числа пороговых булевых функций от п переменных. Для этой задачи, активно исследовавшейся в разных странах еще в 60-х годах нашего столетия, только в 1989 году Зуевым Ю.А. была установлена асимптотика логарифма числа пороговых функций.

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

Если перейти к рассмотрению классов k-значных функций при кгз или частичных k-значных функций при то оказывается, что

даже установление асимптотики log2<p(n) , где ?>(п) - число функций в классе от п переменных, во многих случаях представляет собой трудную задачу. Так, например, в работах Коробкова В.К., который рассматривал задачу оценки числа монотонных k-значных функций, получен только порядок логарифма числа таких функций. Таким •образом, возникает необходимость разработки методов, применимых •. для широкого круга задач оценки числа дискретных функций.

Другая важная проблема при изучении классов дискретных функций состоит в построении достаточно быстрых алгоритмов, которые бы по заданной функции распознавали, входит ли функция в рассматриваемый класс (или обладает ли она заданным свойством). Проблемы этого типа возникают, в частности, в таких приложениях, как распознавание образов и криптография. Известно, что с такими вопросами связана проблема распознавания полноты системы функций в k-значной логике Р^ или частичной k-значной логике Рк, то есть вопрос о том, можно ли суперпозициями данных функций получить

все функции из Рк или Р^.

Впервые вопрос такого типа был рассмотрен, по-видимому, Р.В.

Фрейвалдом (см. Трахтенброт Б. А. Сложность алгоритмов и

вычислений (Спецкурс для студентов НГУ)// НГУ, Новосиб., 1967,

стр. 243-249) . Он рассмотрел задачу о сложности распознавания

полноты системы булевых функций на машине Тьюринга при условии,

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

с разделителем. В соответствии с теоремой Поста, для

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

проверить принадлежность данных функций пяти классам. Фрейвалд

показал, что для каждого из этих классов это можно сделать на •

2

машине Тьюринга с числом операций о(ы ), где N -длина входа, и для распознавания полноты эта оценка неулучшаема по порядку.

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

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

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

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

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

Научная_новизна. Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации получены 'следующие основные результаты:

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

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

3) с использованием метода искусственных ограничений получена асимптотика при к-*» логарифма числа простых базисов в частичной к-значной логике,-

4) с использованием метода искусственных ограничений получена асимптотика логарифма числа различных замыканий на п-элементном множестве,-

5) для случая, когда дискретные функции задаются вектором значений, разработан метод для построения алгоритмов распознавания свойств, заданных через отношения, основанный на сведении исходной задачи к вычислению полилинейных форм над

полукольцами;

6) для использования в методе полилинейных форм разработан метод ускорения вычислений тензорных степеней полилинейных форм, основанный на ступенчатых билинейных разложениях,-

7) с использованием метода полилинейных форм получен

алгоритм (в модели неветвящихся алгоритмов) для распознавания

полноты систем функций в 7-значной логике с битовой сложностью 1 2 й

о(N ), где N - суммарная длина векторов значений всех данных

•7

функций (естественный алгоритм имеет сложность 0(N )) и алгоритм для распознавания полноты систем функций в частичной 2-значной

log 3

логике с битовой сложностью 0(n -logN-loglogN-logloglogN) (естественный алгоритм имеет сложность O(N^)). Получены также нетривиальные результаты о сложности распознавания полноты систем функций в k-значной логике при больших к.

ÛUàEXE^QliàS-H-XêSMlMêÇEM-ûeHUQS.Zk ■ Диссертация носит теоретический характер. Полученные результаты и разработанные методы могут найти применение для получения асимптотических оценок числа различных дискретных объектов и для построения достаточно быстрых алгоритмов распознавания свойств дискретных функций в таких приложениях, как проектирование сложных управляющих систем, распознавание образов, криптография.

АпЕобация_работы. Результаты диссертации докладывались на международной конференции по основам теории вычислений (Казань, 1987), на международной конференции- по методам теории чисел и алгебры в компьютерных науках (Москва, 1993), на международном семинаре по сложности и реализации булевых функций (Дагштул, ФРГ, 1992), на советско-германских семинарах по дискретной математике (Самарканд, 1987, Росток, 1988, Ереван, 1989), на всесоюзных конференциях по проблемам теоретической кибернетики (Новосибирск, 1980, Горький, 1988, Волгоград, 1990), на всесоюзных и межгосударственных семинарах по дискретной математике и ее -приложениям (Москва, 1987, 1990, 1995), на Ломоносовских чтениях в МГУ, на семинарах по математическим вопросам кибернетики под руководством чл.-корр. РАН С.В.Яблонского и семинарах по синтезу управляющих систем и смежным вопросам под руководством чл.-корр. РАН О.Б.Лупанова и с.н.с. В.М.Храпченко, на других конференциях, школах и

семинарах.

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

Структу2а_и_объем_Еабдты. Диссертация состоит из введения, двух глав и списка литературы. Первая глава разбита на 9 параграфов, вторая - на 6. Объем работы 247 страниц. Список литературы содержит 9 8 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В §1.1 описан метод искусственных ограничений для получения асимптотических верхних оценок числа дискретных функций, удовлетворяющих заданным условиям, связывающим значения функции на определенных группах точек области определения V. Суть метода состоит в следующем. Пусть Р - интересующий нас класс и ю -область значений функций. Рассматривается , алгоритм построения некоторого класса т функций, отображающих V в Б, причем так, 'что для |т| легко получить верхнюю оценку. После' этого доказывается,' что рет, что дает верхнюю оценку для |р|. Функции из т задаются последовательно на группах точек из V. При этом кроме естественных ограничений на значения функции на очередной группе точек, возникающих из определения класса Р, дополнительно накладываются искусственные ограничения, чтобы уменьшить количество вариантов на очередной группе точек.

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

t раз, и пусть рассматриваются р разбиений области определения на группы и не более чем к упорядочений этих групп для каждого разбиения. Тогда, если доказано, что fst, то

t t

И

t q

log2|F| s plog2d+log2P+log2K+log2Cp+tlog2-g-Если все параметры зависят от п и при п <° все слагаемые в правой части последнего неравенства бесконечно малы по сравнению с первым слагаемым, то

log2|F| — (1+о(1))-plog2d.

При реализации этой схемы главный вопрос - как вводить искусственные ограничения, чтобы можно было получить достаточно малое d, но при этом оставалось малым t. В диссертации предложены 3 варианта искусственных ограничений. Для двух из них доказаны общие теоремы, дающие верхние оценки числа дискретных функций в общем виде (теоремы 1.1.1-1.1.4), для третьего варианта качественно обоснована его применимость. Далее в главе i с использованием всех этих вариантов метода искусственных ограничений решается ряд задач оценки числа дискретных функций и других объектов на уровне асимптотики логарифма.

В §1.2-1.7 рассматриваются так называемые предполные классы

*

в k-значной логике р^ и частичной k-значной логике р^, играющие определяющую" роль в распознавании полноты систем функций. В §1.2-1.5 полностью решена на уровне асимптотики логарифма задача о числе функций от п переменных в .каждом предполном классе в Рк (число таких классов с ростом к растет как двойная экспонента). В §1.2 рассмотрены классы, для которых результаты получаются достаточно просто без метода искусственных ограничений. В §1.3 с помощью метода искусственных ограничений установлена асимптотика логарифма • числа функций от п переменных в каждом предполном классе, определяемом так называемыми центральными отношениями. Эта асимптотика имеет вид: knlog2d, где d - некоторый параметр, характеризующий степень независимости элементов относительно рассматриваемого отношения.

В §1.4-1.5 рассмотрены оставшиеся предполные классы - классы монотонных k-значных функций, обобщающие класс монотонных

булевых функций. Для решения этой задачи в §1.4 решается трудная комбинаторная задача о поведении для заданного конечного частично упорядоченного множества S ширины w(sn) - максимальной мощности независимого подмножества в декартовой степени sn. Для каждого S установлена асимптотика ширины w(sn) при п а

п 1 kn

именно: w (S ) = • (1+о(1)) (Теорема 1.4.2), Где D

/2nD у/ п~

имеет смысл дисперсии и характеризует разброс элементов множества s. Для получения асимптотики ширины w(sn) используются вероятностные методы, теорема о паросочетаниях и теорема Гейла о потоках в сетях. В §1.5 с помощью этого результата и метода искусственных ограничений для каждого частично упорядоченного

kn

множества S установлена асимптотика вида с-----, где с легко

у/'п

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

В §1.6 рассмотрена задача о числе функций от п переменных в

*

каждом предполном классе частичной 2-значной логики Р2.

Известно, что таких классов 8, причем проблемы вызывают два

класса, определяемые с помощью 4-местных отношений. В § 1.6 с

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

* .

асимптотика логарифма в каждом предполном классе в Р2. В 51.7 с использованием метода искусственных ограничений установлена асимптотика логарифма числа функций от п переменных в каждом предполном классе частичной k-значной логики Рк, определяемом двухместным отношением.

В §1.8 рассмотрена задача о числе так называемых простых, базисов в р^ при к °>. Путем сведения этой задачи к задаче оценки числа некоторых специальных функций и далее с использованием метода искусственных ограничений установлена

асимптотика log2S* (k)-kk ~к! при к <•>.

В §1.9 с помощью метода искусственных ограничений

[-]

установлена асимптотика сп2 для. двоичного логарифма числа различных операций замыкания на n-элементном множестве.

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

развито уже много методов и приемов для построения быстрых алгоритмов, в главе 2 предложен новый подход к проблеме распознавания свойств дискретных функций. Этот подход развивает общую идею перехода от задачи распознавания свойства к задаче вычисления некоторого алгебраического выражения, что позволяет далее использовать хорошую структуру алгебраических систем для ускорения вычислений. Таким образом, основным результатом главы 2 является новый метод, названный методом полилинейных форм, для построения алгоритмов распознавания свойств дискретных функций. В §2.1, 2.3, 2.5 представлены з варианта этого метода, в §2.2, 2.4, 2.6 продемонстрировано, как эти варианты метода полилинейных форм могут использоваться для ускорения распознавания полноты систем функций, заданных таблично, в р^ и

Р2"

В §2.1 описан метод полилинейных форм. Здесь рассматриваются функции к-значной логики или частичной к-значной логики, заданные вектором их значений. Пусть на области определения каждой переменной задано ь-местное отношение и, и пусть функция ± зависит от п переменных. Тогда на ее области определения порождается 1т-местное отношение л11. Пусть на области значений задано ь-местное отношение я . Требуется выяснить-, верно ли, что всегда, когда точки удовлетворяют я11,

значения функции f (а1), . . л(а^)', удовлетворяют Такое

описание свойства функций охватывает многие важные классы дискретных функций. В §2.1 показано, что'указанный вопрос можно свести к вычислению некоторой полилинейной формы над некоторым полукольцом, в которой коэффициенты зависят только от я и числа переменных п у функции, а значения переменных легко вычисляются по вектору значений функции и отношению й (теорема 2.1.1). Более того, если и фиксировано, то все эти формы при разных п можно сделать тензорными степенями одной и той же 1г-линейной формы 0, зависящей только от я и не зависящей от п (лемма 2.1.2). Таким образом, метод полилинейных форм сводит проблему быстрого распознавания свойств дискретных функций в указанной постановке к проблеме быстрого вычисления тензорных степеней формы ф, определенным образом связанной с отношением л. В §2.1 показано, что в результате проблему можно свести просто к

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

В §2.2 с помощью метода полилинейных форм получены некоторые-оценки сложности распознавания полноты системы функций

в Р. и построен алгоритм (рассматривается модель неветвящихся ^ *

алгоритмов) для распознавания полноты систем функций в р2 с

1од,3 .

битовой сложностью ОШ -1од!Мод1од1Мод1од1одЫ) , где N -суммарная длина векторов всех заданных функций (естественный

4

алгоритм имеет сложность о(и )).

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

приближенными разложениями показано, что для распознавания

полноты систем функций в Р7 существует алгоритм с битовой

128 7

сложностью 0(ы • ) (сложность естественного алгоритма 0(ы )).

Так как метод полилинейных форм сводит задачу распознавания

свойств дискретных функций к вычислению тензорных степеней

полилинейной формы, то возникает проблема быстрого решения

последней задачи. В §2.5 предложен новый метод для ускорения

вычислений тензорных степеней полилинейных форм, основанный на

ступенчатых билинейных разложениях исходной полилинейной формы.

В §2.6 метод полилинейных форм на основе билинейных разложений

применен для построения алгоритмов распознавания полноты систем

функций в Рк при больших к с нетривиальной оценкой сложности.

Список литературы

1. Алексеев В. Б. О простых базисах к-значной логики //Математические заметки. - 1969. - Т.5, вып.4. - С.471-482 .

2. Алексеев В.Б. Простые базисы и простые функции в к-значной логике // Кибернетика. - 1971. - 5. - С.137-141.

3. Алексеев В.Б. О числе простых базисов в k-значной логике //Сб."Дискретный анализ". Вып.19 - Новосибирск, 1971. -С. 3-ю.

4. Алексеев В.Б. О числе k-значных монотонных функций //ДАН СССР. - 1973. - Т.208, №3. - С.505-508.

5. Алексеев В.Б. О числе монотонных k-значных функций //Сб. "Проблемы кибернетики". Вып. 28. - М.-. Наука. '- 1974. -С.5-24.

6. Алексеев В.Б. О монотонных функциях k-значной логики //Тезисы докладов 2-й Всесоюзной конференции по математической логике, Москва. - 1972. - С.з.

7. Алексеев В.Б. Использование симметрии при нахождении ширины частично упорядоченного множества //Сб."Дискретный анализ". Вып.26. - Новосибирск, 1974. - С.20-35..'

8. Алексеев В.Б. О сложности нахождения ширины частично упорядоченного множества с симметриями // Тезисы докладов ' 5-й Всесоюзной конференции по проблемам теоретической кибернетики, Новосибирск. - 1980. - С.138-140.

9. Алексеев В.Б. 0 числе функций в классах, задаваемых центральными предикатами //Математические заметки. - 1985. -Т.37, вып.б. - С.880-886 .

ю. Алексеев В.В., Емельянов Н.Р. Метод построения быстрых алгоритмов в k-значной логике //Математические заметки. -1985'. -38, вып.1. - С.148-156.

11. Алексеев В.В., Емельянов Н.Р. Об алгоритмической сложности некоторых задач распознавания в многозначных логиках //Тезисы докладов 7-й Всесоюзной конференции "Проблемы теоретической кибернетики", Иркутск. - 1985. - ч.1. - С.8-9.

12. Алексеев В. Б. 0 числе функций k-значной логики, описываемых центральными . предикатами // 3-й международный рабочий семинар "Математические вопросы -кибернетики. МВК-87". - Тезисы докладов. - Братислава,1987. - С.149-150.

13. Алексеев В. Б. Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках //Известия ВУЗов. Математика. - 1988. - 7. - С.19-27.

14. Алексеев В.Б. О числе простых базисов в классе частичных функций k-значной логики //Тезисы докладов 8-й Всесоюзной конференции "Проблемы теоретической кибернетики", Горький. -1988. - 4.1. - С.14-15.

15. Алексеев В.Б. О числе функций в некоторых замкнутых классах частичной k-значной логики //Дискретная математика. - 1989. - Т.1, вып.1. - С.32-42.

16. Алексеев В.Б. О числе семейств подмножеств, замкнутых относительно пересечения //Дискретная математика. - 1989. -Т.1, ВЫП.2. - С.129-136.

17. Алексеев В. Б. О некоторых алгоритмах вычисления полилинейных форм //Труды семинара по дискретной математике и ее приложениям. - М.:Изд-во Моск. ун-та, 1989. - С.134-137.

18. Алексеев В.Б. Об одном методе получения оценок мощности дискретных множеств//Сб."Проблемы теоретической кибернетики. Тезисы докладов и Всесоюзной конференции (сент.1990г.) ." -Волгоград, 1990. - С.З.

19. Алексеев В.Б. 0 сложности распознавания полноты в Р7 //Сб."Методы и системы технической диагностики". Вып.18. -Саратов: Изд-во Саратовского университета, 1993. - С.э-и. •

20. Alekseyev V.B. Recognition of properties in k-valued logic and approximate algorithms //Lecture Notes in Computer , Science. - 278. - Berlin: Spriger-Verlag. - 1987. - P.10-13.

21. Alexeev V.B. On the number of functions in some maximal closed classes of partial k-valued logic //Rostocker Mathematisches Kolloquium, Heft 39. - Rostock. - 1990. -P.5-12.

22. Alekseyev V.B. Completeness recognition in many-valued logic by use of polylinear forms //Тезисы докладов международной конференции "Number Theoretic and Algebraic Methods in Computer Science", Москва. - 1993. - С.3-5.