О полноте и 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, т), г), т), /(&-, т), Ь (к, т) и У (к, т).

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 Vollstandigkeit 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 Universitat, 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,½, стр. 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 Societe 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.