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

• Подколзина, Мария Александровна
• кандидат физико-математических наук
• 2011

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

1 Основные понятия и результаты.

2 Отношения; тупиковые и приведенные отношения.

3 Понятие 7г-множества. Д-рефлексивные отношения.

4 Семейства отношений Gi(k,r), Ni(k,r), V\(к, г), Li(fc,r), Qo(*,T),Qi(A,T),Q2(fc,T).

5 S-тупиковые отношения. S-критериальность S-тупиковых отношений.

6 Критерий полноты в Р^. S-критериальные системы в Pk.

7 Семейства отношений {Z(k: 1), /3(к, 1),

D(k,l), L(k, 1), N{k, 1)}.

8 S-предполнота S-множеств, принадлежащих классам сохранения отношений из объединения семейств Z(k, 1), N(k, 1), D(k,l),L(k,l)nI(k,l).

9 Семейства отношений Z(k,r), D(k, г), N(k, т), I(к, т), г) и V(k, т). Доказательство теорем 1.4-1.7.

10 О числе S-предполных классов в функциональной системе

11 О полноте вР^и А-полноте S-множеств детерминированных функций, содержащих все одноместные детерминированные S-функции.

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

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

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

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

Центральное место среди функциональных систем принадлежит итеративным функциональным системам, представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификациями [2,3]. Развитие теории итеративных функциональных систем шло по пути изучения конкретных моделей функциональных систем. В 1921 году Е.Постом была полностью описана структура замкнутых классов в двузначной логике — это описание, изложенное в монографии в 1941 году, по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции [4,5,6]. Интерес к изучению итеративных функциональных систем особенно возрос в начале 50-х годов прошлого века в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В 1954 году С.В.Яблонским [7] была решена проблема полноты в трехзначной логике. После появления работы [7] усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных к-значных логиках. Начиная с 60-х годов прошлого века наряду с &-значными логиками стали интенсивно изучаться итеративные функциональные системы, элементами которых являются автоматные отображения [8,9], функции счетнозначных логик [11,12]. Позже появились работы, связанные с изучением итеративных функциональных систем, содержащих в качестве элементов вычислимые функции [12,15], программы и схемы программ [13,16].

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

Как показано в [2] итеративные функциональные системы могут быть разделены на два типа: истинностные функциональные системы и после-довательностные функциональные системы. В первом случае функции, принадлежащие функциональной системе, вычисляются без использования, а во втором — с использованием "памяти".

Среди всех истинностных функциональных систем центральное место занимает функциональная система Р&, состоящая из функций к-значной логики и операций суперпозиции над ними. Это объясняется прежде всего тем, что, во-первых, в большинстве реальных моделей истинностных функциональных систем функции, как правило, конечнознач-ны и, во-вторых, любая функция в каждой истинностной функциональной системе аппроксимируется функциями /г-значных логик путем увеличения числа к. Критерии полноты в Р^ могут быть сформулированы с использованием понятия критериальной системы. Система замкнутых подмножеств множества Р/. образует критериальную систему в Р&, если из непринадлежности произвольного множества функций &-зиачной логики к каждому из подмножеств данной системы следует его полнота. Тривиальным примером критериальной в Р& системы является множество всех собственных замкнутых подмножеств множества Р&. Однако мощность этой критериальной системы континуальна и с ее помощью нельзя получить эффективный критерий полноты в Р^ [21]. Вместе с тем, в функциональной системе Р& существуют конечные полные системы, и любое замкнутое подмножество множества Р& расширяется до предполного в Р% класса (максимальной подалгебры), причем для любого к > 2 число предполиых в Р^ классов конечно. Нетрудно видеть, что всякий предполный класс принадлежит любой критериальной системе, а множество всех предполных классов образует минимальную критериальную систему в Р^. Таким образом, из явного описания множества всех предполных классов следует эффективный и наилучший в определенном смысле алгоритм для распознавания полноты произвольных конечных систем функций &-значной логики. В уже упоминавшихся работах Е.Поста и С.В.Яблонского [4,7] решение задач о полноте в двузначной и трехзначной логиках как раз и было достигнуто путем явного описания множества предполных классов; при этом оказалось, что в Р2 пять, а в Р3 восемнадцать таких классов. Проблема явного описания множества предполных классов в Р& для любого к > 4 долгое время оставалась открытой и оказалась довольно сложной. В 1964 году А.И.Мальцев исследовал задачу о полноте в четырехзначной логиках. С.В.Яблонским [7], А.В.Кузнецовым [21], В.В.Мартышоком [22], JIo Чжу Каем, Пан Юн-цзе, Ван Сяо-хао, Лю Сюй-хуа [23,24,25,26], Е.В.Захаровой [27], И.Розенбергом [28] были последовательно в явном виде построены все предполные классы в &-значных логиках (см. также [29]). Важно отметить, что в этих работах использован аппарат сохранения функциями &-значных логик отношений (предикатов), впервые введенный А.В.Кузнецовым. Именно на этом пути И.Розенбергом было проведено завершающее построение множества всех предполных классов в &-значных логиках, а С.В.Яблонским, Е.Ю.Захаровой и В.Б.Кудрявцевым получена асимптотика их числа [30].

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

В наиболее общей постановке задача о полноте для о.-д. функций изучалась в работах В.Б.Кудрявцева [31] и М.И.Кратко [32]. Как показано в

32] не существует алгоритма для распознавания полноты конечных множеств о.-д. функций. Вместе с тем, функциональная система Р является конечнопорожденной [2] и совокупность предполных классов образует минимальную критериальную систему в Р. Поэтому возникает вопрос: какова мощность множества предполных классов в Р. В [31] (см. также

33]) установлено, что эта мощность равна континууму.

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

Задача о полноте для систем о.-д. функций, содержащих полную истинностную подсистему (т.е. все о.-д. функции с одним состоянием) рассматривалась в работе А.А.Летичевского [34]. Им был получен эффективный алгоритм распознавания полноты конечных систем с указанными свойствами в классе отображений, осуществляемых автоматами Мура. Д.Н. Бабин усилил этот результат, распространив его на случай, когда наряду с полной истинностной подсистемой исследуемая на полноту система содержит произвольное конечное множество о.-д. функций. Кроме того, Д.Н. Бабиным полностью описаны все случаи существования алгоритмов распознавания полноты систем о.-д.функций, содержащих истинностные подсистемы, образующие базисы в произвольных замкнутых классах булевых функций из диаграммы Е.Поста (см. [35] и цитируемую там литературу).

Одной из основных характеристик поведения автоматов (о.-д.функций) является возможность с их помощью представлять регулярные события [36]. Множество Ш1 С Р называется К-полным (Клини-полным), если для всякого регулярного события из о.-д.функций множества можно получить о.-д.функцию, представляющую это событие. В общем случае (Ю.Дассоу [37]) ситуация, возникающая при изучении задачи о Неполноте аналогична той, которая возникает при исследовании задачи о полноте: существует континуум предполных классов и не существует алгоритма для распознавания К-полноты конечных систем о.-д.функций.

С точки зрения приложений важным подклассом Р является множество Ь — отображений, осуществляемых так называемыми линейными автоматами. Задача о полноте в этом множестве рассматривалась А.А.Часовских [38]. В частности, А.А.Часовских установлено, что хотя в Ь счетное число предполных классов, существует алгоритм распознавания полноты конечных систем о.-д. функций из Ь.

Большой, главным образом, теоретический интерес представляет исследование последовательностной функциональной системы, которая отличается от Р тем, что в ней к о.-д.функциям могут применяться только операции суперпозиции. Эта функциональная система изучалась в работах С.В.Алешина и Д.Н.Бабина [39,40,41]. Нетрудно показать [42], что изъятие такой сильной "автоматной" операции, как обратная связь, приводит к тому, что в рассматриваемой функциональной системе нет конечных полных систем. Однако ее элементы — о.-д. функции, достаточно "сложны" и обладают интересными имитационными свойствами. Легко видеть, что множество всех одноместных о.-д.функций замкнуто относительно операции суперпозиции и образует полугруппу. Вместе с тем, множество всех взаимно-однозначных одноместных о.-д.функций образует группу, которая, как показал С.В.Алешин [43], содержит бесконечную, периодическую и конечнопорожденную подгруппу. Вопрос о существовании таких групп составляет содержание известной ослабленной проблемы Бернсайда [44]. Указанная подгруппа порождается явно всего двумя элементами, представляющими собой о.-д.функции с семью и тремя состояниями. Как отмечено выше, в множестве всех о.-д.функций не существует конечных полных систем, если пользоваться только операциями суперпозиции. Поэтому естественно возникает следующая важная проблема (аналог 13 проблемы Д.Гильберта): можно ли для всякого п > 3 любую п-местную о.-д.функцию представить в виде суперпозиции (тг — 1)-местных. Оказалось, что эта проблема решается положительно. Более того, в [41] показано, что любую о.-д.функцию можно выразить через суперпозицию одноместных о.-д.функций и единственной двухместной о.-д.функции, которая имеет одно состояние и образует полную истинностную систему.

Кроме функциональных систем, содержащих в качестве элементов о.-д. функции, рассматривались также последовательностные функциональные системы, элементами которых являются детерминированные функции (д.функции), а операциями — те же операции суперпозиции и обратной связи. В этой функциональной системе любое полное множество континуально и, как установлено В.Б.Кудрявцевым [2], существует гиперконтинуум предполных классов. С.С.Марченковым показано, что для любого п > 2 существуют д.функции от п переменных, которые нельзя представить через суперпозицию д.функций от меньшего числа переменных [45].

Анализ содержательных моделей последовательностных функциональных систем показывает, что решение задачи о полноте в этих системах наталкивается на трудности недостаточной эффективности. Исключение составляет функциональная система функций с задержками, которая занимает промежуточное положение между конечнозначными логиками и автоматными отображениями (В.Б.Кудрявцев [8,9]). Однако элементы этой системы представляют собой лишь весьма частный случай о.-д.функций, а используемые в ней операции синхронной суперпозиции значительно "слабее" операций суперпозиции и обратной связи. Таким образом, возникает необходимость в разработке принципиально иных подходов к исследованию задачи о полноте в последовательностных функциональных системах.

В силу своего определения о.-д.функции являются бесконечными и даже континуальными функциями. Таким образом, предполагается, что вычисляющий любую о.-д.функцию автомат "работает" бесконечно долго. Однако с точки зрения приложений совершенно очевидно, что каждое реальное кибернетическое устройство (в том числе, автомат) по истечении некоторого конечного промежутка времени прекращает свою "работу", т.е. либо становится ненужным, либо переводится в начальное состояние. В связи с этим естественно возникает

Задача о полноте в последовательностной функциональной системе •

Пусть к > 2, г > 1. Элементами функциональной системы являются детерминированные функции, переменные которых принимают значения из Е]. — множества всех слов длины т, составленных из букв алфавита Еь = {0,1,., к — 1}. В качестве операций в функциональной системе Р£ рассматриваются операции суперпозиции и обратной связи. Заметим, что любая функция из Р£ может быть "вычислена" конечным автоматом за первые т тактов его работы. Нетрудно видеть также, что для любого т > 1 множество всех о.-д.функций естественным образом гомоморфно отображениям на множество д.функций из

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

В [36] показано, что для решения задачи о полноте в Р£ операция "обратная связь" оказывается несущественной, т.е. в данном случае эта операция выразима через операции суперпозиции. Отсюда легко следует, что задача о полноте в конечнозначных логиках — одна из основных задач в теории истиностных функциональных систем, эквивалентна задаче о полноте в т.е. при г = 1. Вместе с тем, при г > 2 существует принципиальное различие между функциональной системой, элементами которой являются функции &-значных логик, и функциональной системой Р£. Множество всех детерминированных отображений, рассматриваемых на словах длины т, порождает специальное замкнутое подмножество в &т-значных логиках, существенно зависящее от двух параметров — параметра к и параметра т. Используя естественную аналогию между задачей полноты в Р£и в конечнопорожденных замкнутых классах конечнозначных логик, можно ввести понятие предполного класса в Р£ и показать, что всякое множество является полным в Р^" тогда и только тогда, когда оно целиком не содержится ни в одном из предполных в Р£ классов; совокупность предполных классов в Р£ конечна, может быть описана эффективно и образует минимальную критериальную систему для распознавания полноты систем функций из Р£; при этом множество предполных классов в Р£ изоморфно некоторому подмножеству предполных классов в Р£. Таким образом, в отличие от задачи о полноте в Р для любых к > 2, г > 1 существует алгоритм для распознавания пол ноты в PI произвольных конечных множеств д.функций. Также как в fc-значных логиках, каждый из этих алгоритмов может быть задан с использованием эффективно описываемых критериальных систем, а наилучший из них получается на пути явного описания всех предполных классов в Р£.

В общем случае для любых к > 2, т > 1 задача о полноте в PJ. решена В.А.Буевичем в [46,47,48,49]. В терминах сохранения отношений описаны все предполные классы в Р£. Однако это описание оказалось довольно сложным. В частности, отношения, классы сохранения которых совпадают с предполными в Р£ классами, могут иметь любую арность от 1 до fcr, а их число даже при малых кит очень велико. В связи с этим естественной представляется задача об исследовании на полноту систем детерминированных функций, которые обладали бы некоторыми наперед заданными, но вместе с тем достаточно общими свойствами.

Настоящая диссертация посвящена рассмотрению задачи о полноте в Р£ так называемых S-множеств, состоящих только из S-функций — детерминированных функций, вычисляемых конечными автоматами, в каждом состоянии которых реализуется функция /г-значной логики, принимающая все к значений. Легко видеть, что для любой функции , жп) из Р£ существует S-функция д(хi,., хП1 xn+i), также принадлежащая PJ. такая, что f(x\, • • • 1 %п) = • • • 1 Яти

По аналогии с общим случаем в диссертации введено понятие S-предполного класса и показано, что произвольное S-множество 9R С Р£ является полным в PJ тогда и только тогда, когда 971 не содержится ни в одном из S-предполных в PJ. классов. Таким образом, возникает задача об описании множества всех S-предполных в PJ. классов. Отметим, что задача в случае, когда т = 1, т.е. в к-значных логиках решена В.Б.Кудрявцевым [50].

В диссертации с использованием аппарата сохранения отношений для любых к > 2, т > 1 представлено описание всех S-предполных классов в Р^. Оказалось, что совокупность отношений, классы сохранения которых совпадают с S-предполными, распадается на шесть семейств — семейства Z(k,r), D(k, г), N(k, г), I(k: г), L(k,r) и V(k,r). Семейство Z(k,r) состоит из унарных отношений, отношения, принадлежащие семействам D(k, г), N(k, г), 1{к, г)и V(k, т) бинарны, а отношения, принадлежащие семейству L(k, т) имеют арность, равную четырем. При этом семейства Z(k, 1), D(k, 1), N(k, 1), I(к, 1) и L(k, 1) совпадают с теми, которые описаны в [50]. Заметим, что каждый S-предполный в PJ. класс является в то же время одним из предполных классов в PZ", однако описание Sпредполных классов значительно проще, чем описание всех предполных классов в полученное в [46,47,48,49].

С задачей полноты в тесно связана задача об А-полноте в -Ро.д. [36,50]. Учитывая детерминированность функций из -Ро.д. можно, очевидно, считать, что для всякого т > 1 эти функции определены также на всех наборах слов длины Пусть т > 1. О.-д.функция д(х1,., хп) и д.функция /(жх,., хп) являются т-эквивалентными, если для любого набора слов (а^ . ,ап), каждое из которых имеет длину г, выполнено равенство д{а\,., ап) = /(аь ., ап). Подобным образом определяется т-эквивалентность множеств из -Ро.д. и из Р^. Множество 91 С Ро.д. называется А-полным, если для любого т > 1 замыкание множества ОХ т-эквивалентно Р£. Известно, [50] что в общем случае не существует алгоритма для распознавания А-полноты конечных систем о.-д.функций. Поэтому представляет интерес поиск такого алгоритма для систем о.-д.функций, обладающих некоторыми наперед заданными свойствами.

Диссертация состоит из введения и двенадцати параграфов. В $$ 19 для любых к > 2, т > 1 дано полное решение задачи о Б-полноте в Щ — с использованием аппарата сохранения отношений описано множество всех Э-предполных в Р£ классов. Совокупность отношений, классы сохранения которых совпадают с Э-предполными в Р£ классами разбивается на шесть семейств — семейства Z(k,т), г), т), /(&,т), Ь(к,т) и У(к,т).

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

1. Кон П. Универсальная алгебра // Москва, Мир, 1968.

2. Кудрявцев В.Б. Функциональные системы // Москва, Изд-во МГУ, 1982

3. Мальцев А.И. Итеративные алгебры Поста // Новосибирск, Изд-во СО АНСССР, 1976

4. Post Е. Two-valued iterative systems of mathematical logic // Prinston, 1941

5. Яблонский C.B., Гаврилов Г.П, Кудрявцев В.Б. Функции алгебры логики и классы Поста // Москва, Наука, 1966, 177стр.

6. Угольников А.Б. Классы Поста // Москва, Изд-во Центра прикладных исследований при мех.-мат. МГУ, 2008, 64 стр.

7. Яблонский С.В. Функциональные построения в &-значных логиках // Труды МИАН СССР, т.51, стр.5-142, 1958

8. Кудрявцев В.Б. Вопросы полноты для автоматов // ДАН СССР, 1960, т.130, №6, с.1189-1192

9. Кудрявцев Б.£>.Теорема полноты для одного класса автоматов без обратных связей // ДАН СССР, 1960, т.132, №2, с.272-274

10. Гаврилов Г.П О функциональной полноте в счетно-значной логике //В кн. "Проблемы кибернетики", вып.15, Москва, Наука, 1965, с.5-64

11. Деметрович Я.О мощности множеств преклассов в предельных логиках // Acta Cybernetika, 1972, t.l, Fase.4, Szeged, s.233-239

12. Лавров И.А. Использование арифметических прогрессий к-го порядка для построения базисов алгебры примитивно-рекурсивных функций // ДАН СССР, 1967, т. 172, "2, с.279-282

13. Редько В.Н. Основания композиционного программирования// Программирование, 1979, №3, с.9-19

14. Глушков В.М. О полноте системопераций в электронных вычислительных машинах // Кибернетика, Киев, 1968, №2, с.1-15

15. Голунков Ю.В. К теории систем алгоритмических алгебр // ДАН СССР, 1977, т.232, №4, с.749-752

16. Тайманов В.А. О функциональных системах к-значной логики с операциями замыкания программного типа // ДАН СССР, 1984, т.286, №6, с.1307-1310

17. Янов Ю.И., Мучник A.A. О существовании &-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР, 1959, т.127, №1, с. 44-46

18. Алексеев В. Б. О полупростых базисах fc-значной логики // Мат.заметки, 1985, т.38, М, с.44-46

19. Марченков С. С. Существование базисов по суперпозиции в счетных примитивно-рекурсивных замкнутых классах //Мат.заметки, 1986,т.39, №2, с. 268-276

20. Горлов B.B. О замкнутых классах Ахзначной логики, все конгруэнции которых тривиальны // Мат. заметки, 1977, №4, с.499-509

21. Кузнецов A.B. Математика в СССР за сорок лет // Москва, 1959, т. 1, $13, с.102-115

22. Мартынюк В. В Исследование некоторых классов функций в многозначных логиках //В кн. "Проблемы кибернетики", вып.З, Москва, Наука, 1960, с.49-60

23. JIo Чжу Кай, Лю Сюй-хуа Предполные классы, определяемые ьинарными отношениями в многозначных логиках // Acta Sei. natur. Univ. Yilinensis, 1963, v.4

24. Пан Юн-цзе Один разрешающий метод для отыскания всех пред-полных классов в многозначных логиках // Acta Sei. natur. Univ. Yilinensis,1962, v.2

25. Захарова Е.Ю. Критерий полноты систем функций в // В кн. "Проблемы кибернетики", вып. 18, Москва, 1967, с.5-10

26. Rosenberg Y. Uber die functionale Vollständigkeit in den mehrwertigen Logiken. Praha, Rozpravi Ceskoslovenska Acodemie Ved. v. 80, №4, p. 393,1970

27. Буевич В. А. Вариант доказательства критерия полноты для функций к-значной логики. Москва, Дискретная математика, т.8., вып.4, стр. 11-36, 1996

28. Захарова Е.Ю., Кудрявцев В.Б., Яблонский C.B. О предполных классах в k-значных логиках. ДАН СССР, т.136, №3, стр.509-512, 1969

29. Кудрявцев В.Б. О мощности множеств предполных множеств некоторых функциональных систем, связанных с автоматами // В кн. "Проблемы кибернетики", вып. 13, Москва, Наука, 1965, с.45-74

30. Кратко М.И. Алгоритмическая неразрешимость распознавания полноты для конечных автоматов // ДАН СССР, 1964, т.155, №1, с.35-37

31. Родин A.A. О предполных классах в множестве автоматных отображений // Материалы конференции "Современные проблемы математики, механики и их приложений", Москва, 2009, с. 372

32. Лебичевский A.A. Условия полноты в классе автоматов Мура // В кн. Материалы научных семинаров по теоритическим и прикладным вопросам кибернетики, вып.2, Киев, 1963

33. Бабин Д.Н. Классификация автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Москва, изд-во МГУ, 2009, 111 стр.

34. Кудрявцев В.Б., Алешин С.В., Водколзин A.C. Введение в теорию автоматов // Москва, Наука, 1985.

35. Dassow У Ein modifizierter Vollstandig-keiin einer Algebra von Automatenabbildungen // Dissertation Doctor B.Rostock Universität, 1978

36. Часовских A.A. О полноте в классе линейных автоматов //В кн. Математические вопросы кибернетики. Вып.З, Москва, Наука, 1991, с.140-166

37. Алешин С. В. О суперпозициях автоматных отображений // Кибернетика, Киев, 1975, с.29-34

38. Алешин С. В. Об отсутствии базисов в некоторых классах инициальных автоматов //В кн. Проблемы кибернетики, вып. 22, Москва, Наука, 1970, с.67-75

39. Бабин Д.В. О полноте двухместных о.-д.функций относительно суперпозиции // Москва, Дискретная математика, 1989, т.1, вып.4, с.86-91

40. Яблонский С. В. Введение в дискретную математику, Москва, "Наука" 1986

41. Алешин С. В. Конечные автоматы и проблема Бернсайда в периодических группах // Москва, Мат. заметки, 1972, вып.З, с.319-328

42. Карганов М.И., Мерзляков Ю.И. Основы теории групп //Москва, Наука, 1982, 214 стр.

43. Марченков С. С. Об одном методе анализа суперпозиций непре-рывныфункций //В кн. Проблемы кибернетики, вып.37, Москва, Наука, 1985, с. 5-18

44. Буевич В.А. О т-полиоте в классе автоматных отображений. Докл. АН СССР 1980. - Т. 252, № 5 - с. 221-224.

45. Буевич В.А. Условия А-полноты для конечных автоматов, ч.1 Москва, Изд-во МГУ, 1986

46. Буевич В.А. Условия А-полноты для конечных автоматов, ч.2 Москва, Изд-во МГУ, 1987

47. Буевич В.А. О т- полноте в классе детерминированных функций Докл. РАН, т.326, №3, стр.399-403, 1992

48. Кудрявцев В.Б. О свойствах S-систем функций k-значной логики. Elektronische Informationsverarbeitung und Kybernetik. EIK 9,1/2, стр. 8105, 1973

49. Буевич В.А. Об алгоритмической неразрешимости распознавания А-полноты для ограниченно-детерминированных функций //Математические заметки. 6, Москва, 687-697, 1972

50. Буевич В.А., Клиндукова Т.Э. О существовании алгоритма для распознавания A-полноты систем, содержащих все одноместные ограниченно-детерминированные функции //Математические вопросы кибернетики.8, Москва, Наука, 289-297, 1999.

51. Slupeski Y. Kryterium petnosci wielowartosciowych systemow logici zdan // Comptes rendus des seanses de la Société des Sciences et des Lettres de Varsovie, 102-109, 1939

52. Salomaa A. On basis groups for the set of functions over a finite domain //Ann.Acad. Sci. Finnicae, Ser A 338, 1-15, 1963

53. Буевич В.А., Подколзииа M.А. Критерий полноты S-множеств детерминированных функций. //Математические вопросы кибернетики, 16, Москва, Физматлит, 191-238, 2007

54. Буевич В.А., Подколзина М.А. Задача о полноте S-множеств детерминированных функций // Вестник Московского университетата. Сер.1. Математика. Механика., 2008, № 5, с. 57-59

55. Буевич В.А., Подколзина М.А. О полноте S-множеств детерминированных функций // тезисы докладов 9 Междунар. семинара "Дискретная математика и ее приложения", Москва, 2007

56. Подколзина М.А. О числе S-предполных классов в функциональной системе //Вестник Московского университета. Сер.1. Математика. Механика., 2008, № 6, с. 43-45

57. Подколзина М.А. К задаче о полноте S-множеств детерминированных функций // тез. докл. между.конференции "Современные проблемы математики, механики и их приложений", Москва, 2009, с. 370-371

58. Подколзина М.А. О полноте и А-полноте S-множеств детерминированных функций, содержащих все одноместные детерминированные S-функции // Дискретная математика, том 21, вып.2, Москва, 2009, с. 75-88