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

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

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

Содержание

1 Введение

«

3

2 Основные понятия

3 Алгоритмы построения векторов коэффициентов полиномов

3.1 Алгоритм построения вектора коэффициентов полинома по вектору функции в &-значной логике

3.2 Алгоритм построения вектора коэффициентов поляризованного полинома по вектору функции в /г-значной логике

3.3 Экспериментальные результаты к главе 3

4 Исследование периодических функций

4.1 Булевы функции в классе поляризованных полиномов

4.2 Исследование функций трехзначной логики периода длины 4

4.3 Преобразование в применении к периодическим функциям

4.4 Общие утверждения о сложности периодических функций

4.5 О структуре матриц

4.6 Исследование функций пятизначной логики с периодами длины 6

4.7 Исследование функций пятизначной логики с периодами длины 7

4.8 Экспериментальные результаты к главе 4

4.9 О сложности периодических функций к—значной логики большого периода

5 Заключение 72 А Сложные функции от малого числа переменных

4

В Ранг матриц

Введение диссертации (часть автореферата) на тему «О сложности функций κ-значной логики в классе поляризованных полиномов»

1 Введение

Одной из основных составляющих дискретных моделей являются функции к—значной логики. Они начали изучаться в 50-е годы прошлого века в связи с развитием вычислительной техники. Фундаментальными вопросами в данной области являются вопросы полноты, выразимости, канонических форм и другие [34].

Одним из стандартных способов задания функций к—значной логики являются полиномы. Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.И.Жегалкина [12, 13]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения вне этой области.

Только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых функций. В работах Д. Мюллера [52] и И. Рида [53] полиномы Жегалкина были переоткрыты и получено их обобщение для введения нового класса линейных кодов, получивших название «коды Рида-Мюллера», а введенные полиномиальные формы стали называться «формами Рида-Мюллера».

Появление интереса непосредственно к полиномиальным представлениям булевых функций как объектам исследования связано с практическими приложениями. Развитие электроники во второй половине двадцатого века в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привело к тому, что большая интеграция имеет определяющее значение. Лучшей считается схема, имеющая меньшую площадь кристалла. Этот критерий плюс технологические требования регулярности структуры привели к требованию отображать на кристалл функцию или систему функций в виде дизъюнктивной, конъюнктивной или полиномиальной нормальной формы — матричной схемы. Такие схемы получили название программируемых логических матриц (ПЛМ) [2,3,7,8,56-58].

Более того, в последние годы полиномиальные представления булевых и к—значных функций находят и другие применения, например, в задачах машинного обучения, кодирования и защиты информации [44,46-51]. Они широко используются в теории сложности при нахождении нижних оценок сложности схем [24,35-37,55]. Полиномиальные представления также применяются в комбинаторно-графовых задачах [38,42,43].

При простых к любая функция к—значной логики представима полиномом по модулю к [34]. При составных к существуют не полиномиальные функции. Кроме того,. полиномиальные формы можно понимать в различных обобщенных смыслах. Исследуются различные поляризованные (понятие поляризации вводится по-разному) полиномиальные формы [4,5,27,28], полиномы над кольцом целых чисел [39], обощенные полиномы [14,26,40], квазиполиномы [29], кронекеровы матричные формы [6].

В теории управляющих систем важной задачей является получение нижних (и точных) оценок сложности для конкретных функций. Например, в классе схем из функциональных элементов к настоящему времени найдены только линейные нижние оценки сложности индивидуальных функций, в то время как мощностным методом доказано, что почти все функции являются «сложными» [16,54]. Модель поляризованных полиномов является одной из моделей, для которой удается строить нелинейные нижние оценки сложности индивидуальных функций. Для булевой логики Н. А. Перязевым были построены индивидуальные последовательности «сложных» в классе поляризованных полиномов функций. При к ^ 3 для к—значной логики вопрос построения последовательностей сложных функций пока остается открытым.

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

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

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

. Для булевой логики первые оценки функции Шеннона были опубликованы Т. Бавао и Р. ВезвНсЬ в [57], потом которые были улучшены В. П. Супруном в [31]. Точное значение функции Шеннона в классе полиномиальных поляризованных форм было найдено Н. А. Перязевым в [23]. Для случаев к—значной логики при к^З известные к настоящему времени верхняя [27] и нижняя [1] оценки функции Шеннона совпадают лишь по порядку роста. Интерес к исследованию сложности функций в классе поляризованных полиномов объяс-

няется тем, что в настоящее время при проектировании цифровых устройств применяются программируемые логические матрицы (ПЛМ) типа РЬХСЖС. Основой для'проектирования устройств на базе ПЛМ такого типа являются канонические поляризованные полиномы реализуемых булевых функций. Известные оценки функции Шеннона в классе поляризованных полиномов устанавливают необходимое и достаточное число промежуточных шин ПЛМ для реализации произвольных булевых функций от п переменных.

При исследовании функции Шеннона сложности функций в классе поляризованных полиномов оказались полезны последовательности периодических функций. Функция называется периодической с периодом р, если вектор ее значений представляет собой многократно повторяющийся вектор р. Последовательностью периодических функций называется последовательность функций {/¿} от I переменных с одинаковыми периодами. Сложность последовательности периодических функций определяется как функция от количества переменных пив каждой точке равна сложности соответствующей периодической функции. Последовательности периодических функций, сложность которых есть о малое от функции Шеннона, будем называть вырожденными. Последовательности функций, не являющиеся вырожденными, назовем невырожденными.

В настоящей работе получены следующие результаты:

• Представлен быстрый алгоритм преобразования вектора значений функции к—значной логики в вектор коэффициентов ее поляризованного полинома.

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

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

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

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

значности логики к и экспоненциальный по длине периода Т.

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

• Для к—значной логики найден критерий невырожденности семейств последовательностей периодических функций, сводящий вопрос о невырожденности семейств функций к вычислительной задаче полиномиальной по значности логики к и длине периода Т. <

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

Основные результаты диссертации опубликованы в [17-22,25] и были представлены автором на следующих конференциях:

• XV международная конференция «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.)

• VIII Международная научная конференция «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009 г.)

• X Международный семинар «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.) ,

• XVI международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011 г.)

• XI Международный семинар «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012 г.)

• Научная конференция «Тихоновские чтения» (Москва, 29 октября - 2 ноября 2012 г.)

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

Во второй главе вводятся основные понятия.

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

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

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

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

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

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

В третьем параграфе вводится преобразование моделирующее итерацию преобразования вектора значений функций А;—значной логики в вектор коэффициентов поляризованного полинома применительно к периодическим функциям.

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

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

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

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

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

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

2 Основные понятия

Пусть к ^ 2, Ek = {0,1,..., к — 1}. Функция f(xn) называется функцией к—значной логики, если на всяком наборе а £ ЕЦ ее значение содержится в Ek. Совокупность всех функций к—значной логики от п переменных обозначается через PJ}. Для функции к—значной логики /(жо>х\,...,хп-\) ее г—й остаточной функцией (г £ Ek) по переменной xq будем называть функцию /г(жь Х2, ■ ■ ■, xn-i) — /(г, Х\,Х2, •.., £n_i). Каждую функцию А;—значной логики можно задавать вектором ее значений ак" = (о;о5 скъ ..., &кп-i)> где координата аг — это значение функции на наборе, представляющем запись числа i в к—ичной системе счисления.

Полиномом назовем такую сумму (все суммы и произведения берутся по mod к)

Е с/(й) • хо.....

а=(а0,...,ап_1)еЯ£

в котором df(a) £ Ek — некоторые коэффициенты.

Поляризованным по вектору поляризации а = (оо,... ,crn-i) £ полиномом назовем сумму (все суммы и произведения берутся по mod к)

Е caf(a) ■ {х0 + <70)ао.....(жп-1 +

а=(а0,...!ап-1)€Е£

в котором cj(a) £ Ek — некоторые коэффициенты, и (хг + аг)а1 — степени, то есть

(хг + аг)а' = 1 • (хг + аг) ■ (хг + аг).....(хг + аг).

а, раз

Ясно, что, если а = (0,..., 0), то поляризованный по вектору а полином -обычный полином по mod к.

Под записью Ра будем понимать полином, поляризованный по вектору а. Каждая функция f(xn) £ PJ} однозначно задается полиномом по модулю к [33]. В [27] показано, что для каждого вектора поляризации а £ Е

t

каждая функция f(xn) G PJ} пред ставима поляризованным по вектору а полиномом единственным образом. Далее в работе будем везде считать, что к — простое число. Под к всюду далее будет пониматься значность логики.

Назовем вектором коэффициентов поляризованного по вектору поляризации er G Е^ полинома функции f(xn) G Р£ вектор значений функции с^(хп).

Обозначим за К вектор всевозможных элементарных произведений п переменных, в котором они упорядочены лексикографически, то есть для j G Е%п верно Kj = x%qX%i ... где выражение ¿o^i... in — запись числа j в к—ичной системе счисления.

Тогда / =< р,К >, если р — вектор коэффициентов полинома функции /, а < • , • > — скалярное произведение векторов.

Сложностью 1(Ра) полинома, поляризованного по вектору а, назовем число слагаемых с ненулевыми коэффициентами. Сложность функции А;-значной логики / в классе поляризованных полиномов определяется как минимальная по всем векторам поляризации а G Eß сложность полинома Ра, реализующего функцию /.

LH) = min l(Pa).

Функция Шеннона Lfc(n) определяется как сложность самой сложной функции к—значной логики от п переменных в классе поляризованных полиномов.

Первая нижняя оценка функции Шеннона для булевой логики была получена в 1990 году Т. Sasao и Р. Beselich [57]:

I/2 (n) ^ 2 • 2п/2 - 2, для четных п.

В 1993 году В. П. Супруном была получена верхняя и улучшена нижняя оценка функции Шеннона [31]:

1/2(п) < 3 • 2П-2, для п ^ 2;

и

/ п

Ып) > г /91 V [п/щ,

Точное значение функции Шеннона для булевой логики в 1995 году было найдено Н. А. Перязевым'[23]:

"оп+Г

Ь2(п) =

где [•] обозначает целую часть.

Для функций к—значной логики верхняя оценка функции Шеннона была получена С. Н. Селезневой в 2002 году [27]:

к(к -1) + Г •

В 2003 году нижняя мощностная оценка функции Шеннона была опубликована В. Б. Алексеевым, А. А. Вороненко и С. Н. Селезневой [1]:

Ьк(п) >

Точное значение функции Шеннона от единицы было в 2004 году найдено С. Н. Селезневой [28]

Ьк(1) = к-1

Для трехзначной логики в 2006 году в дипломной работе Е. Н. Денисова [11] экспериментально было установлено, что при п ^ 10 имеет место оценка

Ьз{п) ^

^ОП

4

3 Алгоритмы построения векторов коэффициентов полиномов

Эта часть работы посвящена построению алгоритма преобразования векторов значений функций /с-значной логики в векторы коэффициентов их поляризованных полиномов.

Подобные алгоритмы в булевом случае для неполяризованных полиномов можно найти в [10], а для поляризованных — в [30], а также в таких зарубежных работах, как [41,45].

Случай к-значной логики для неполяризованных полиномов был исследован Ю. В. Таранниковым (не опубликовано).

3.1 Алгоритм построения вектора коэффициентов полинома по вектору функции в /с-значной логике

Докажем две вспомогательные леммы. (Ранее они доказывались, например, в [15]). Будем иметь в виду, что в формулировках и доказательствах все арифметические операции производятся по модулю к.

Лемма 3.1.1. [15] Для каждого простого к верно, что

у> Г"1' Р = к-1 ^ \ 0,

Доказательство.

Рассмотрим сначала случай р = к — 1. Тогда по малой теореме Ферма

к-1

г=1

В случае 1 ^ р ^ к — 2 доказательство проведём по индукции. Базис индукции (р — 1).

2

г=1

в силу чётности числа к — 1. Индуктивный переход. . Допустим, что лемма верна для всех 1 ^ р ^ т — 1 ^ А; — 3, и проверим справедливость для р = т:

/с—1

о = кт+1 = ((г + 1)ш+1 - гт+1) =

г=0

= Е ((т + ^ + Ш(т2+1)*т-1 • ■ • + (т + 1)г + 1) .

Тогда, пользуясь предположением индукции, получаем к-1 / , ы

г=0 г=0

+ {т-1)т(т+1)!£.т_2+ +!£. + к = 0

г=0 г=0

Но т + 1 не может быть сравнимо с нулем по модулю А;, следовательно,

к-1

г=0

Лемма доказана.

'."ДёМма 3.1.2. Если'к - простое число, то

к-А . . л (■ \

— (—1),где - биномиальный коэффициент.

э ) V/

Доказательство.

к - Л (к — 1)! _ {к-1){к-2)...(к-э) _ 3 ) ~{к-1-т~ з\

1 • 2 • ... • 3 1 ;

Лемма доказана.

Пусть пит — натуральные числа, и заданы некоторые векторы а = (а?!, ¿¿2, • • •, с*п) и ¡3 = (/?1, /?2, • • •, Рт)- Тогда записью (а, Р) будем обозначать вектор (ск1,ог2, • • ., оп,■ ■ ■,Рт)•

Теперь над векторами из Е%п определим (индукцией по п) следующее преобразование Ск'-

а) если п = 1 и а = (ого, ■ ■ ■, ак-1) , то

Ск(а) = ( а0)-^г* 2оц,..., - ^го», - ^

к-1 /с—1 А;—1

О,;

г=0 г=0 г=0

б) Предположим, что операция уже определена для каждого вектора из Е%п и рассмотрим произвольный вектор

= (а?0,а(Ап+1_1)) = (а0, а1,..., ак~г), где а* е Е%п, г € Я*.

о

Пусть

...,

,, . , (D

известны по индуктивному предположению. Положим

(fc-i fc-i fc-i \

i=О г=0 г=0 /

где сумма векторов подразумевается как покомпонентная.

Преобразование Ck при п — 1 будем называть элементарным.

Теорема 3.1.3. Пусть к - простое число. Вектор af значений функции f(xn) G Pk связан с вектором pf коэффициентов полинома Р(хп), реализующего функцию f(xn), следующим образом: pf = Ck(6if).

Доказательство.

Для доказательства проведем индукцию по количеству переменных п. Базис индукции (n = 1).

Пусть / — функция /с-значной логики от одной переменной, с* — коэффициенты при г-той степени переменной, тогда

/(0) = с0,

/(г) =с0 + гс1 + ... + г*_1с*_1, (г = 1,..., к - 1). Покажем, что

СО = /(0), fc-i

cm = -y£/ik-1-mf{%),{m=l,...,k-2),

г=1 к-1

Ск-1 = ~ •

г=0

Заметим, что первое очевидно и проверим второе и третье. Применяя лемму 3.1.1, получаем

к-1 fc-l к-1 к-1 / fc-1

= -Е^Е«^ = ЕсЛ-Е

г=1 г=1 .7=0 j=0 \ г=1

Проведем еще одну цепочку преобразований, подставив выражения (1) и применяя лемму 3.1.1:

к-1 к-1 к-1 к-1 к-1

г=0 i=0 j=0 j=0 г=0

fc-1-m+j , _ п

- WI1'

4

Тогда р/ = С*;(а/). Базис индукции обоснован. Далее условимся, что 0° = 1. Тогда

- ' - ' " к-1

г=0

Индуктивный переход.

Пусть теорема верна для некоторого п ^ 1. Проверим ее справедливость для п + 1.

Разложим вектор значений а = (с*о> а^+г-х) функции /(хп+1) на к

компонент:

а0 = (а0,а1,...

а1 = (акп, акп+1,..., ос2кп-\),

Тогда а1 можно рассматривать как вектор г-ой остаточной функции

/¿(хь х2, ...,хп) = /(г, хъ х2, ■ ■ ■, хп). По индуктивному предположению

...,

Ск{ак-1) = (рк0-\РкГ\■ ■ ■ А*пЛ) = Р*-1-Пусть хп = {х\,х2, ■ ■ ■ ,хп). Тогда выразим /, представив /г полиномами,

ё

«

воспользовавшись индуктивным предположением и леммой 3.1.2:

. /(¿п+1) = Мхо)Мхп) + лЫЛ(^) + • • • + Зк-1{хо)}к-1{хп) = = (1 -'4_1)7о + (1 - (*0 - I)""1)/! + • • • + (1 - (хо - (к -

к—1

г=0

= Ё - 4"1 - Е(-1У ~ ^ 4*-1-' - <?,&>--

к—2 к-1 / /с-1

=< К > - 4 2< К > +4-1 - 2 < к >

¿=1 г=0 \ г=0

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Маркелов, Николай Константинович

5 Заключение

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

• Представлен быстрый алгоритм преобразования вектора значений функции к—значной логики в вектор коэффициентов ее простого поляризованного полинома (теоремы 3.1.4, 3.2.2).

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

• Для трехзначной логики улучшена нижняя оценка функции Шеннона в классе поляризованных полиномов и представлены периодические функции, на которых эта оценка достигается (теоремы 4.2.9 и 4.2.10).

• Для пятизначной логики доказана вырожденность и невырожденность некоторых последовательностей периодических функций (теоремы 4.6.5 и 4.7.12).

• Для к—значной логики найден критерий невырожденности последовательностей периодических функций, сводящий вопрос о невырожденности конкретных функций к вычислительной задаче полиномиальной по значности логики к и экспоненциальной по длине периода Т (теоремы 4.4.3 и 4.4.5).

• Получена нижняя оценка сложности последовательностей невырожденных функций к—значной логики в классе поляризованных полиномов (теорема 4.4.4).

• Для к—значной логики найден критерий невырожденности семейств последовательностей периодических функций, сводящий вопрос о невырожденности семейств функций к вычислительной задаче полиномиальной по значности логики к и длине периода Т (теоремы 4.4.6 и 4.4 7).

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

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

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

[1] Алексеев В.В., Вороненко A.A., Селезнева С.Н. О сложности реализации функций k-значной логики поляризованными полиномами // Труды V Международной конференции «Дискретные модели в теории управляющих систем». М.: МАКС Пресс, 2003. С. 8-9.

[2] Артюхов B.JL, Копейкин Г.А., Шалыго A.A. Настраиваемые модули для управляющих логических устройств. Ленинград: Энергоиздат, 1981. 166 с.

[3] Ачасова С. M. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь, 1987. 135 с.

'"[4}~БШгюк'А'. СГ Сложные в полиномиальных поляризованных формах симметричные булевы функции //XII Международная конференция по проблемам теоретической кибернетики: Тезисы докл. Нижний Новгород, 1999. С. 17.

[5] Балюк А. С. Сложные в полиномиальных поляризованных формах функции алгебры логики // Тезисы докладов международной конференции по математической логике. Новосибирск, 1999. С. 9-10.

[6] Балюк A.C., Добрынина Ю.А. Нижняя оценка сложности к-значных функций в классе кронекеровых матричных форм Синтаксис и семантика логических систем // Материалы 4-й Российской школы-семинара, посвященной 80-летию основания Бурятского государственного университета. Улан-Удэ, 2012. С. 20-22.

[7] Баранова С. И., Скляров В. А. Цифровые устройства на программируемых СБИС с матричной структурой. М.: Радио и связь, 1986. 270 с.

[8] Бибило П. Н. Синтез комбинационных ПЛМ структур для СБИС. Минск: Наука и техника, 1992. 232 с.

[9] Виноградов И. М. Основы теории чисел. М.-Л., Гостехиздат, 1952. С. 29, 47-48.

[10] Гаврилов Г.П., Сапоженко A.A. Задачи и упражнения по дискретной математике. М.: Физматлит, 1977. С. 52-58.

[11] Денисов E.H. О сложности функций трехзначной логики в классе поляризованных полиномов. Дипломная работа, кафедра математической кибернетики, ВМиК МГУ им. Ломоносова, 2006.

[12] Жегалкин И. И. Арифметизация символической логики // Мат. сборник.

1928. Т.35. С.311-373.'

[13] Жегалкин И. И. Арифметизация символической логики // Мат. сборник.

1929. Т.36. С.305-338.

[14] Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика, т. 17, вып. 3,

:и,2005. С. 80-88.

[15] Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.

[16] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. Вып. 14 М.: Наука, 1965. С. 31-110.

[17] Маркелов Н. К. Селезнева С. Н. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов к—значных функций // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики». Казань: Отечество, 2008. С. 102.

[18] Маркелов Н. К. О сложности некоторых k-значных функций в классе поляризованных полиномов // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, 1—6 февраля 2010 г.). М.: Издательство механико-математического факультета МГУ. С. 191-193.

[19] Маркелов Н. К. О сложности периодических функций трехзначной логики в классе поляризованных полиномов // Материалы XVI Международной конференции (Нижний Новгород, 20—25 июня 2011 г). Изд-во Нижегородского госуниверситета, 2011. С. 301-303.

[20] Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. 2012. №3. С. 40-45.

[21] Маркелов Н.К. Критерий невырожденности периодических функций к—значной логики // Материалы X Международного семинара «Дискретная математика и ее приложения»(Москва, 18—23 июня 2012 г). С. 199-202.

[22] Маркелов Н.К. О сложности в классе поляризованных полиномов периодических функций к—значной логики с периодами большой длины // Научная конференция «Тихоновские чтения», тезисы докладов (Москва, 29-31 октября 2012 г). М.: МАКС Пресс, 2012. С. 50.

[23] Перязев H.A. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика, т. 34, вып. 3. 1995. С. 323-

vK-;326. ,

[24] Разборов А. А. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения // Матем. заметки, ДАН СССР 41:4. 1987. С. 598-607.

[25] Селезнева С.Н., Маркелов Н. К. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов к—значных функций // Ученые записки Казанского университета Сер. Физико-математические науки, Т. 151, вып. 2. 2009. С. 147-153.

[26] Селезнева С.Н., Дайняк А.Б. О сложности обобщенных полиномов А;—значных функций / / Вестник Моск. У нив. Серия 15. Вычисл. матем. и кибернетика. 2008. С. 34-39.

[27] Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика том 14, выпуск 2. 2002. С. 48-53.

[28] Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной // Дискретная математика том 16, выпуск 2. 2004. С. 117—120.

[29] Селезнева С. Н. О сложности k-значных функций в одном классе полиномов // Проблемы теоретической кибернетики. Материалы XVI международной конференции. Нижний Новгород: Издательство Нижегородского госуниверситета, 2011. С. 430-434.

[30] Супрун В.П. Табличный метод полиномиального разложения булевых функций // Кибернетика. 1987. №1. С. 116-117.

[31] В. П. Супрун, Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика, том 5, выпуск 2. 1993. С. 111-115.

[32] Шалыто А. А. Логическое управление. Методы аппаратной и программной реализации. СПб.: Наука, 2000. 780 с.

[33] Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001. С. 9-42.

' [34] Яблонский С. В. 'Функциональные построения в к—значной логике // '

Труды математического института им. В. А. Стеклова АН СССР. Т. 51. 1958. С. 5-142.

[35] Aspnes J., Beigel R., Furst M., Rudich S. The expressive power of voting polynomials // Combinatorica, vol. 14, no. 2. 1994. P. 135-148

[36] Beigel R. The polynomial method in circuit complexity // Structures in Complexity Theory: 8 th Annual Conference. 1993. P. 82-95.

i

[37] Beigel R., Reingold N., Spielman D. The perceptron strikes back // Proceedings of the Sixth Conference on Structure in Complexity Theory. 1991. P. 286-291.

[38] Efremenko K. 3-query locally decodable codes of subexponential length //

In Accepted to the 41 st Annual Symposium on the Theory of Computing *

(STOC'09). ACM. 2009. P. 39-44.

[39] GopalanP., Shpilka A., Lovett S. The Complexity of Boolean Functions in Different Characteristics // Computational Complexity vol. 19, no. 2. 2010. P. 235-263.

[40] Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions // IEEE Trans. Elect. Comput. 1967. P. 671-674.

i

[41] Falkowski B.J., Rahardja S. Efficient computation of quaternary fixed polarity Reed-Muller expansions // IEE Proc. Comput. Digit. Tech., Vol. 142, No. 5. 1995. P. 345-352.

[42] Grolmusz V., Superpolynomial size set-systems with restricted intersections

mod 6 and explicit Ramsey graphs // Combinatorica, vol. 20, no. 1. 2000. P. ,

71-86.

[43] Gopalan P. Constructing Ramsey graphs from Boolean function representations // In Proceedings of the 21 st IEEE Conference on Computational Complexity (CCC'06). 2006. P. 115-128.

79

i

[44] Jackson J., Klivans A., Servedio R. Learnability beyond AC 0 // m Proceedings of the 34th ACM Symposium on Theory of Computing. 2002. P.

> 7-7-6—784. - — *

[45] Jankovic D., Stankovic R.S., Moraga C. Optimization of arithmetic expressions using the dual polarity property // 1st Balkan Conference in Informatics, BCI 2003, Thessaloniki, Greece. 2003. P. 402-410.

[46] Klivans A. Servedio R. Learning DNF in time 2°(nl/3) //in Proceedings of t the 33rd Annual Symposium on Theory of Computing (STOC'Ol). 2001. P. 258-265.

[47] Kushilevitz E., Mansour Y. Learning decision trees using the Fourier spectrum // SIAM J. on Computing, vol. 22, no. 6. 1993. P. 1331-1348.

[48] Linial N., Mansour Y., Nisan N. Constant depth circuits, Fourier transform and learnability // Journal of the ACM vol. 40, no. 3. 1993. P. 607-620.

[49] Mac Williams F., Sloan N. The Theory of Error-Correcting Codes. North-Holland, 1977. 762 p.

[50] Minsky M. Papert S. Perceptrons: an Introduction to Computational Geometry. MIT Press, 1968. 292 p.

[51] Mossel E., O'Donnell R., Servedio R. Learning juntas //In Proceedings of i the 35 th Annual ACM Symposium on the Theory of Computing (STOC'03).

2003. P. 206-212.

[52] Muller D. E. Application of Boolean algebra to switching circuit design and to error detection // IRE Trans. Electron. Comput. EC-3. 1954. P. 6-12.

[53] Reed I. S. A class of multiple-error-correcting codes and the decoding scheme // IRE Trans, on Inform. Theory. 1954. P. 38-49.

V

[54] Shannon C.E. The synthesis of two-terminal switching circuits. // Bell Syst. Techn, vol. 28, no. 1. 1949. P. 59-98.

[55] Smolensky R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity //In Proceedings of the 19 th Annual ACM Symposium

on Theoretical Computer Science (STOC'87). 1987. P. 77-82. ,

[56] Sasao T. Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexyty of Programmable Logic Arrays // IEEE Trans, on Comput, vol. 30, no. 9. 1981. P. 633-645.

[57] Sasao T., Besslich P. On the complexity of mod-2 sum PLA's // IEEE Trans, on Comput, vol. 39, no. 2. 1990. P. 262-266.

[58] Wood R.A. A Higt Density Programmable Logic Array Chip // IEEE Trans, vol. 29, no. 9. 1979. P. 602-608.

i

i

t

\