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

• Часовских Анатолий Александрович
• доктор наук
• 2021

Оглавление диссертации доктор наук Часовских Анатолий Александрович

Введение

Глава 1. Постановка задач, вспомогательные классы

1.1. Линейный автомат, операции композиции

1.2. Аппроксимационная полнота

1.3. Класс одноместных ЛА, сохраняющих нулевую последовательность

Глава 2. Проблема полноты для линейных автоматов

2.1. Редукция

2.2. Приведенная ^-критериальная система

2.3. Об алгоритме проверки полноты

Глава 3. Замкнутые классы, содержащие сумматор

3.1. Необходимые понятия и обозначения

3.2. Замкнутые классы одноместных линейных автоматов, сохраняющих нулевую последовательность

3.3. Об алгоритме проверки выразимости через конечные множества

с сумматором

3.4. Выразимость сумматора через конечные множества

Глава 4. Аппроксимационная выразимость в классе линейных автоматов через множества, содержащие существенный автомат

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

4.2. Аппроксимационная выразимость через множества линейных автоматов с существенным автоматом, замыкания которых содержат все константы

4.3. Аппроксимационная выразимость всех констант через множества линейных автоматов, содержащие существенный автомат

4.4. Достаточные условия аппроксимационной выразимости

4.5. Об основаниях систем с сумматором, для которых выразимость

и аппроксимационная выразимость равносильны

4.6. Структура аппроксимационно замкнутых множеств линейных автоматов, содержащих сумматор в аппроксимационном замыкании

Глава 5. О полноте в некоторых содержательных классах

5.1. Линейные автоматы с операциями суперпозиции

5.2. Класс линейных 2-адических автоматов

Заключение

Список сокращений и условных обозначений

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

Введение диссертации (часть автореферата) на тему «Полнота и выразимость в классах линейных автоматов»

Введение

Актуальность темы. Интерес к автоматам, как преобразователям накапливающим и обобщающим поступающую в дискретные моменты времени информацию благодаря возможности менять свое внутреннее состояние, возник с середины прошлого столетия. Начало теории автоматов было положено работами Дж. фон-Неймана [54], С. К. Клини [36], М. Л. Минского [51], Э. Ф. Мура [53].

Возможность моделирования автоматами процессов обработки информации живыми организмами и бурное развитие вычислительной техники обусловили интенсивные исследования в области теории автоматов и их обобщений. Работа [53] Э. Ф. Мура об отличимости состояний конечного автомата и работа [36] С. К. Клини о представимых конечными автоматами событиях задали начальное направление развития теории. Решения задачи об автоматах в лабиринтах, полученные Л. Будахом [89] и А. С. Подколзиным [18], положили начало многочисленным исследованиям поведения конечных автоматов в сложных средах.

Одним из важных направлений исследований стала структурная теория автоматов, развиваемая в работах научной школы кибернетики, основателями которой являются А. А. Ляпунов, В. М. Глушков, С. В. Яблонский, О. Б. Лу-панов, Р. Г. Бухараев, В. Б. Кудрявцев. В рамках структурной теории решаются задачи, связанные с выразимостью через заданные множества конечных автоматов при использовании некоторого "естественного" набора операций. В качестве операций, как правило, при этом выбираются операции суперпозиции, перенесенные из классов функций, не обладающих памятью, или операции композиции, включающие помимо суперпозиций операцию обратной связи.

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

которых было положено Дж. фон-Нейманом [102] и Э. Ф. Муром [95]. Предложенная модель исследовалась в работах Е. А. Гото [91], Д. Майхилла [96], А. С. Подколзина [59]-[61], А. А. Болотова [15], И. В. Кучеренко [43] и других авторов.

Ввиду существенных современных результатов, достигнутых в областях, связанных с моделированием восприятия и поведения биологических существ, в последние годы возникла потребность к теоретическим исследованиям в классах искусственных нейронных сетей, рекуррентный вариант которых также является обобщением конечных автоматов. В 1982 году Д. Хопфилд предложил использовать рекуррентные нейронные сети для сжатия данных и моделирования ассоциативной памяти [93]. В дальнейшем были предложены архитектуры рекуррентных нейронных сетей, позволившие получить практически значимые решения для задач автоматического распознавания речи, перевода, распознавания сцен в видеоряде и других. К таким архитектурам следует отнести сеть с долговременной и кратковременной памятью (англ. Long short term memory, LSTM)[92], управляемый рекуррентный блок (англ. Gated recurrent units, GRU) [90].

Известно, что для класса конечных автоматов с операциями суперпозиции отсутствуют конечные полные системы. Ситуация меняется при переходе к операциям композиции. Несмотря на конечнопорожденность этого класса конечных автоматов, исследование полноты его конечных подмножеств затруднено, с одной стороны, по причине континуальности количества максимальных собственных подклассов, называемых предполными классами [40], с другой стороны, отсутствием алгоритма для определения полноты конечных подмножеств [38]. Сложность класса конечных автоматов показана в работе С. В. Алешина [4] о вложенности в этот класс группы Бернсайда.

Возникшие трудности преодолевались несколькими путями, среди которых следует выделить следующие три: изменение понятия замыкания, возможность использования некоторого "естественного" множества автоматов, изуче-

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

А. А. Летичевским был получен критерий полноты множеств автоматов Медведева (автоматов без выходов) при использовании специальной операции замыкания[45].

Д. Н. Бабиным для каждого замкнутого класса решетки Поста [65] определено, является ли алгоритмически разрешимой проблема проверки полноты конечных множеств конечных автоматов, если к этим множествам добавлять данный замкнутый класс [8], [9]. В дальнейшем Д. Н. Бабиным для автоматов с ^-значными входами и выходами были найдены достаточные условия на добавки предполных классов из , которые обеспечивают алгоритмическую разрешимость или сохраняют неразрешимость проверки полноты конечных множеств [10].

Неразрешимость задачи полноты в классе дефинитных автоматов, являющемся одним из содержательных автоматных подклассов, показана Д. Н. Жуком [32]. Оказалось, что этот класс содержит континуум предполных классов [33].

Исследованию свойств конечных автоматов посвящено значительное количество работ, имеющих важное теоретическое и прикладное значение. Отметим здесь работы в области защиты информации [24], [55], построения датчиков псевдослучайных последовательностей [50], распознавания образов [49], [13], разработки компьютерных систем обучения [6], прогнозирования [25], вычисли-

тельной техники [30], технической диагностики [14], исследования различных свойств автоматов и их обобщений [3], [7], [21], [22], [31], [35], [37], [52], [5658], [62], [64]. Следует выделить теорию вероятностных автоматов [98], [19], [1]. Широкий спектр свойств конечных автоматов используется в образовательном процессе [23], [27], [42], [2].

Степень разработанности темы исследования. Инициальный конечный автомат А может быть задан шестеркой (А, , В, ф,\Ь, qo) [42], где А, и В - конечные множества, называемые входным алфавитом, алфавитом состояний и выходным алфавитом, соответственно, ф : А х ^ , 'ф : А х ^ В -функции переходов и выходов, соответственно, q0 - некоторый элемент множества называемый начальным состоянием. Обрабатывая последовательность а, а = а(0), а(1),..., а(£),..., состоящую из элементов входного алфавита, автомат А последовательно переходит в состояния q(1), q(2),... , q(t + 1),... и вычисляет выходные значения Ь(0), Ь(1),..., Ъ(£),..., где

q(0) = qo, q(t + 1) = Ф а(*)) ,

ь(^) = ф т, т)

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

Таким образом, автомат А сопоставляет каждой бесконечной последовательности (сверхслову) а элементов входного алфавита сверхслово ¡3,

р = Ь(0), Ь(1),..., ЬВД,...,

из элементов выходного алфавита и задает ограниченно-детерминированную функцию [42]

/а : ^ В

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

Пусть к - натуральное число, являющееся натуральной степенью некоторого простого числа р. Через Ек мы обозначаем конечное поле (поле Галуа) из к элементов. Конечный автомат А, задаваемый шестеркой (А^, В,ф,ф, до), называется линейным автоматом (ЛА) над полем Еь, если найдутся такие натуральные числа п, в, что А = Е^, = ЕЦ. и В = Ек, а ф и ф - линейные операторы ^-значной логики. Таким образом, мы используем определение ЛА из работы [29], которое включает исследование оптимизации схемной реализации ЛА. Значительное число работ посвящено исследованиям свойств ЛА [100] и [63].

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

Множество всех ЛА над полем Ек обозначим £. Ранее для множества £2, рассматриваемого вместе с операциями композиции (переименования переменных, отождествления переменных, подстановки и обратной связи), были найдены все предполные классы. Оказалось, что таких классов счетное число, но задача проверки конечных подмножеств из £2 на полноту алгоритмически разрешима [67], [68].

Цели и задачи диссертации:

Цели диссертации:

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

2. Решить проблему существования алгоритма, проверяющего полноту конечных подмножеств этих классов и, при положительном решении, построить этот алгоритм.

3. Исследовать выразительные свойства операторов замыкания в классе линейных автоматов над полем из двух элементов через подмножества этих автоматов с естественными допущениями.

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

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

1. Для классов , рассматриваемых вместе с операцией аппроксимационно-го замыкания, найти все предполные классы. Построить алгоритм проверки аппроксимационной полноты конечных множеств ЛА.

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

3. Для конечных полей Ек найти все предполные классы в классах ЛА, рассматриваемых вместе с операциями композиции. Получить приведенную критериальную систему замкнутых классов.

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

5. Изучить структуру замкнутых по операциям композиции подклассов £2, содержащих сумматор. Получить алгоритм проверки выразимости через конечные подмножества из £2 при использовании сумматора и операций

композиции. В рассматриваемом классе найти критерий выразимости сумматора.

6. При "естественных" ограничениях на подмножества из £2 получить критерии аппроксимационной выразимости через эти подмножества.

7. Найти все предполные по операциям суперпозиции классы в £2. Сравнить композиционный, суперпозиционный и аппроксимационный операторы замыкания на множестве £2.

8. Используя технику, разработанную для ЛА, решить задачу полноты для линейных 2-адических автоматов, рассматриваемых вместе с операциями композиции, то есть найти в указанном классе все предполные подклассы, получить алгоритм проверки полноты конечных подмножеств.

Объект и предмет исследования. Объектом исследования является класс линейных автоматов над конечным полем из к элементов. Наиболее полно выразительные свойства линейных автоматов изучены для случая к = 2. Рассатривается также класс линейных 2-адических автоматов.

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

Научная новизна диссертации. В работе решена проблема полноты для классов ЛА над конечными полями. Часть результатов обобщают полученное ранее решение проблемы полноты для ЛА над полем из двух элементов, рассматриваемых вместе с операциями композиции. При этом, в основном, сохранился подход к решению, использованному для указанного частного случая. Сначала были найдены все аппроксимационно предполные классы и получен алгоритм проверки аппроксимационной полноты конечных подмножеств. За-

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

Для построения множества всех предполных по операциям композиции классов в £, помимо обобщения ранее построенных для случая поля Е2 классов, понадобилось найти принципиально новые классы, возникающие в случае полей Галуа, не являющихся простыми. Разработанная автором техника, опирается на некоторые результаты о подкольцах трансцендентных расширений конечных полей, например, на теорему Люрота о структуре подполей трансцендентного расширения конечного поля, содержащих это конечное поле, но включает и более общие алгебраические построения. Для построения предполных классов в £ и нахождения инвариантов, сохраняемых при операциях композиции, потребовалось использовать известные теоремы о структуре полей Галуа и их множеств автоморфизмов.

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

Для случая к = 2 решена задача выразимости через подмножества с сумматором при использовании операций композиции (К-выразимости). Найдена структура замкнутых по операциям композиции классов, содержащих сумматор. Получен алгоритм проверки ^-выразимости сумматора через конечные множества ЛА, а, в случае положительного решения, ^-выразимости через это

множество произвольного линейного автомата.

Известно [42], что для решения задачи аппроксимационной выразимости (А-выразимости) не требуется операция обратной связи. С использованием этого результата в настоящей работе решено несколько задач об А-выразимости. Сначала, в качестве вспомогательного результата, решена задача А-выразимости в алгебре одноместных ЛА, сохраняющих нулевое сверхслово, что позволило получить теорему об А-выразимости через множества ЛА, содержащих существенный автомат, а также все константы в своем аппроксимационном замыкании (А-замыкании). Также получен критерий А-выразимости констант через заданное множество ЛА, содержащее существенный автомат, позволяющий проверять это свойство для конечных множеств ЛА. Кроме перечисленного, в работе получены некоторые достаточные условия, позволяющие проверять А-выразимость ЛА через заданное конечное подмножество . Показана ко-нечнопорожденность невырожденных А-замкнутых множеств ЛА, содержащих сумматор, и, как следствие, их счетность.

Разработанная для ЛА техника позволила найти все предполные классы для £2, рассматриваемого вместе с операциями суперпозиции, а также распространить использованный в работе подход на множество линейных 2-адических автоматов, рассматриваемое вместе с операциями композиции. Для этого класса также найдены все максимальные собственные подалгебры и получен алгоритм проверки полноты конечных подмножеств.

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

Исследования, выполненные для трансцендентных расширений конечных

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

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

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

Методология и методы исследования.

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

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

Автором были исследованы вспомогательные алгебры с операциями, имеющими меньшие ограничения, чем операции композиции в рассматриваемых классах ЛА. Далее решение осуществлялось путем переноса свойств вспомогательных подалгебр на классы £ с изменениями, позволяющими преодолеть возникающие при этом ограничения. Следовательно, для решения проблемы полноты в классах ЛА над конечными полями автором была неоднократно ис-

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

Положения, выносимые на защиту:

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

2. Несмотря на бесконечность множества предполных классов, составляющих приведенную критериальную систему в классе ЛА, для конечных подмножеств таких автоматов получен алгоритм проверки полноты. Этот алгоритм имеет полиномиальную временную сложность от нескольких параметров.

3. Основу используемой техники составляют методы, изложенные в книге [29]. В настоящей работе разработана техника, позволяющая при определенных условиях сводить исследования операций над многоместными ЛА к операциям в алгебре одноместных ЛА. При этом используется разложение изучаемых автоматов в сумму одноместных. Элементы этой алгебры одноместных ЛА, сохраняют нулевое сверхслово и составляют подколь-цо трансцендентного расширения поля Галуа, которое обозначено через Е'к(£). В этой алгебре, рассматриваемой вместе с операциями сложения и умножения, а также некоторой частичной операцией "ослабленного деления", найдены все максимальные подалгебры. В случае простого поля

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

Алгебра Е'к (£) используется как при решении проблемы К-полноты в £, так и при исследовании вопросов К - и А-выразимости в £2.

4. В классе £2 решена проблема ^-выразимости через конечные множества, содержащие сумматор, а также задача выразимости сумматора через такие множества. Для этого в алгебре Е'2(£) выделено счетное семейство

г = 0,1, 2,..., замкнутых классов, каждый из которых не содержит единицу. Каждому ^-замкнутому множеству ЛА, содержащему сумматор, соответствует (в некотором смысле) единственное замкнутое подмножество в Е'2(^), которое не содержится ни в одном из классов семейства или, что равносильно, не содержит единицу. Найдена структура всех таких замкнутых подмножеств множества Е'2(^), которая зависит от наличия в замкнутом подмножестве дроби с положительной степенью. Это позволило определить структуру конечнопорожденных невырожденных ^-замкнутых классов, содержащих сумматор от трех переменных.

5. В структуре замкнутых классов алгебры Е'2(£) найдена подструктура замкнутых по операциям одноместного аппроксимационного замыкания, А(1)-замыкания, классов, которая является счетной, а каждый ее элемент ко-нечнопорожден. Получен алгоритм проверки включения д € А(1\М) для любого конечного подмножества М алгебры Е'2(^) и любого ее элемента д.

6. Получен алгоритм проверки А-выразимости через конечные подмножества ЛА из £2, содержащие существенный автомат (автомат, имеющий две или более непосредственных переменных, то есть переменных, от зна-

чения которых в некоторый момент времени значение выхода зависит в тот же момент времени), а также все константы в А-замыкании. Показано, что любое невырожденное множество ЛА М содержит конечное подмножество М' такое, что А-выразимость всех констант через М равносильна их А-выразимости через М'. Найден алгоритм проверки А-выразимости всех констант через конечные множества ЛА.

7. Получены некоторые достаточные условия для возможности проверки А-выразимости в £2 через конечные множества ЛА. При некоторых "естественных" ограничениях на множества ЛА получено необходимое и достаточное условие совпадения операторов К-замыкания и А-замыкания.

8. Для множества £2 ЛА вместе с операциями суперпозиции найдены все предполные классы, количество которых оказалось счетным. Найденное множество предполных классов составляет приведенную критериальную систему по операциям суперпозиции.

9. Проблема полноты решена для класса линейных 2-адических автоматов, рассматриваемых вместе с операциями композиции. В этом классе также построена счетная критериальная система, состоящая из всех предполных классов. Здесь, как и в случае ЛА, используется возможность декомпозиции автоматов и перехода к исследованию класса одноместных автоматов.

Степень достоверности результатов. Все результаты диссертации математически строго доказаны.

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

• XIII Международном научном семинаре «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, 2019 г.)

• научной конференции "Ломоносовские чтения" (Москва, 2018 г., 2016 г., 2014 г., 2013 г., 2012 г., 2011 г., 2010 г.)

• XI международной конференции "Интеллектуальные системы и компьютерные науки"(Москва, 2016 г.}

• XII Международном научном семинаре «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, 2016 г.)

XI Международном научном семинаре «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, 2012 г.)

международной конференции «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика В. А. Садовничего (Москва, 2009 г.)

Результаты диссертации неоднократно докладывались на специальных семинарах механико-математического факультета МГУ:

• "Теория автоматов" под руководством заведующего кафедрой МаТИС профессора В. Б. Кудрявцева (2012 - 2019 гг.}

• "Математические вопросы кибернетики" под руководством профессора О. М. Касим-Заде (2019 г.)

• "Дискретная математика и математическая кибернетика" под руководством профессора С. А. Ложкина и профессора В. Б. Алексеева (2019 г.)

• "Вопросы сложности алгоритмов поиска" под руководством профессора Э. Э. Гасанова и научных сотрудников В. В. Осокина, Ю. С. Шуткина, Г. В. Калачева (2017 г.)

• "Дискретный анализ" под руководством профессора С. В. Алешина, профессора В. А. Буевича и старшего научного сотрудника М. В. Носова (2016 г.)

Публикации. Материалы диссертации опубликованы в 22 работах автора, из них 15 статей в рецензируемых научных изданиях, рекомендованных для защиты в диссертационном совете МГУ по специальности 01.01.09 - Дискретная математика и математическая кибернетика [66, 67, 74-84, 86, 87], кроме того, 1 статья опубликована в издании из Перечня ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени доктора наук, индексируемом РИНЦ [73].

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

Список литературы диссертационного исследования доктор наук Часовских Анатолий Александрович, 2021 год

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

1. Аблаев Ф. М. О сравнительной сложности вероятностных и детерминированных автоматов // Дискретная математика. — 1991. — Т. 3, № 2. С. 114-120.

2. Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов // М.: Изд. отдел ф-та ВМиК МГУ, 2000. — 58 с.

3. Алексеев Д. В. Приближение функций нескольких переменных нейронными сетями // Фундамент. и прикл. матем. — 2009. — Т. 15, вып. 3. — С. 9-21.

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

5. Алешин С. В., Пантелеев П. А. Конечные автоматы и числа // Дискретная математика. — 2015. — Т. 27, вып. 4. — С. 3-20.

6. Алисейчик П. А., Вашик К., Кудрявцев В. Б., Перетрухин В. В., Строга-лов А. С. Об автоматном моделировании процесса обучения // Дискретная математика — 1996. — Т. 8, вып. 4. — С. 3--10.

7. Андреев А. Е., Часовских А. А. Автоматная сложность двуместных булевых базисов // Дискретная математика — 1996. — Т. 8, вып. 4. — С. 123--133.

8. Бабин Д. Н. Разрешимый случай задачи о полноте автоматных функций // Дискретная математика. — 1992. — Т. 4, № 4. С. 41-55.

9. Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Докл. РАН. — 1999. — Т. 367, № 4. — С. 439-441.

10. Бабин Д. Н. О классификации базисов в Рк по разрешимости проблемы полноты для автоматов // Фундамент. и прикл. матем. — 2009. — Т. 15, № 3. С. 33-47.

11. Бабин Д. Н. Автоматы с суперпозициями, пример нерасширяемости до пред-полного класса // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 3. — С. 87-93.

12. Бабин Д. Н., Летуновский А. А. О возможностях суперпозиции, при наличии в базисе автоматов фиксированной добавки из булевых функций и задержки // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 3. — С. 71—78.

13. Бабин Д. Н., Мазуренко И. Л., Холоденко А. Б. Автоматные языки с частотным свойством естественных языков // Интеллектуальные системы в производстве. — 2013/ — № 1. С. 9-13.

14. Богомолов А. М., Грунский И. С., Сперанский Д. В. Контроль и преобразования дискретных автоматов / М.: URSS, 1975. — 174 с.

15. Болотов А. А. О задачах сводимости и выразимости для однородных структур со входами и выходами // М.: ДАН СССР. — 1980.—Т. 254, № 1. — С. 14-16.

16. Боревич З. И., Шафаревич И. Р. Теория чисел / Изд. 3. — М: Наука, Гл. ред. физ.-мат. лит., 1985. — 504 с.

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

18. Будах Л. Лабиринты и автоматы // Проблемы кибернетики. — 1978. — Вып. 34. — С. 83-94.

19. Бухараев Р. Г. Основы теории вероятностных автоматов / М: Наука, 1985. — 288 с.

20. Ван дер Варден Б. Л. Алгебра / М.: Наука, 1976. — 648 с.

21. Ветренникова Е. В. Построение простейшей универсальной о.-д. функции // Математические вопросы кибернетики. — 1988. — Вып. 1. — С. 237-241.

22. Волков Н. Ю. Автоматная модель преследования // Интеллектуальные системы. — 2007.— Т. 11, вып. 1-4. — С. 749-752.

23. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике / М.: Наука, 1977. — 368 с.

24. Галатенко А. В. Автоматные модели защищенных компьютерных систем // Интеллектуальные системы. 2007. — Т. 11, вып. 1-4. — С. 403-418.

25. Гасанов Э. Э. Прогнозирование периодических сверхсобытий автоматами // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 1. — С. 23-34.

26. Гасанов Э. Э., Мастихина А. А. Прогнозирование общерегулярных сверхсобытий автоматами // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 3. — С. 127-154.

27. Гашков С. Б., Фролов А. Б. Дискретная математика / М.: Юрайт, 2018. — 448 с.

28. Гербуз В. Г. О связи функций автомата и автоматной функции // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 2. — С. 135-142.

29. Гилл А. Линейные последовательностные машины / М.: Наука, 1974. — 288 с.

30. Глушков В. М. Синтез цифровых автоматов / М.: Физматгиз, 1962. — 476 с.

31. Елкин В. И., Высоцкий М. Н. О связи между декомпозициями автоматов и формальных грамматик // Моделирование, декомпозиция и оптимизация сложных динамических процессов. — 2011. — Т. 26, № 1. — С. 24-31.

32. Жук Д. Н. О неразрешимости проблемы полноты для дефинитных автоматов // Интеллектуальные системы. — 2008. — Т. 12. — С. 211-228.

33. Жук Д. Н. Континуальность множества предполных классов в классе дефинитных автоматов // Фундаментальная и прикладная математика. — 2009. — Т. 15, вып. 4. — С. 29—36.

34. Зарисский О., Самюэль П. Коммутативная алгебра: в 2 т. / М.: ИЛ, 1963. — 2 т. 444 с.

35. Карацуба А. А. Решение одной задачи из теории конечных автоматов // УМН. — 1960. — Т. 15, Вып. 3. — С. 157-159.

36. Клини С. К. Представление событий в нервных сетях и конечных автоматах // Автоматы. — М.: ИЛ, 1956. — С. 15-67.

37. Коршунов А. Д. О перечислении конечных автоматов // Проблемы кибер-

нетики. — 1978. — Вып. 34. — С. 5-82.

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

39. Кудрявцев В. Б. Теорема полноты для одного класса автоматов без обратных связей // Проблемы кибернетики. — 1962. — Вып. 8. — С. 91-115.

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

41. Кудрявцев В. Б. О полноте для функциональных систем // ДАН СССР. — 1981. — Т. 257, № 2. — С. 274-278.

42. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов / М.: Наука, 1985. — 320 с.

43. Кучеренко И. В. О структуризации класса обратимых клеточных автоматов // Дискретная математика. — 2007. — Т. 19, № 3. С. 102-121.

44. Ленг С. Алгебра / М.: Мир, 1968. — 564 с.

45. Летичевский А. А. Условия полноты для конечных автоматов // ВМ и МФ. — 1961. — № 4. С. 702-710.

46. Летуновский А. А. Выразимость линейных автоматов относительно расширенной суперпозиции // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 1. — С. 161-170.

47. Лидл Р., Нидеррайтер Г. Конечные поля: в 2 т. / М.: Мир, 1988. — Т. 1. 425 с.

48. Лунц А. Г. -адический аппарат в теории конечных автоматов // Проблемы кибернетики. — 1965. — Вып. 14. — С. 17-30.

49. Мазуренко И. Л. Автоматные методы распознавания речи: диссертация на соискание ученой степени кандидата физ.-мат. наук. — М., 2001. — 119 с.

50. Михалев А. В., Нечаев А. А. Цикловые типы семейств полилинейных рекур-рент и датчики псевдослучайных чисел // Математические вопросы крип-

тографии. — 2014. — Т. 5, вып. 1, — С. 95-125.

51. Минский М. Л. Некоторые универсальные элементы для конечных автоматов // Автоматы. — М.: ИЛ, 1956. — С. 163-178.

52. Миронов А. М. Морфизмы реакции для автоматов в категориях: диссертация на соискание ученой степени кандидата физ.-мат. наук. — М., 1992. — 151 с.

53. Мур Э. Ф. Умозрительные эксперименты с последовательными машинами // Автоматы. — М.: ИЛ, 1956. — С. 179-210.

54. Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонент // Автоматы. — М.: ИЛ, 1956. — С. 68-139.

55. Носов В. А. О связи периодов состояний и периодов выходов автономных автоматов // Лесной вестник. — 2007. — Вып. 2. — С. 144-149.

56. Пантелеев П. А. Об отличимости состояний автоматов // Дискретная математика. — 2003.— Т. 15, вып. 3. — С. 76-90.

57. Пантелеев П. А. Об отличимости состояний решетчатых автоматов // Интеллектуальные системы. — 2005.— Т. 8, вып. 1-4. С. 529-542.

58. Пантелеев П. А. Об отличимости состояний автомата при искажениях на входе // Интеллектуальные системы. — 2007.— Т. 11, вып. 1-4. С. 653-678.

59. Подколзин А. С. О сложности моделирования в однородных структурах // Проблемы кибернетики. — М.: Наука, 1975. — Вып. 30. — С. 199-225.

60. Подколзин А. С. О поведениях однородных структур // Проблемы кибернетики. — М.: Наука, 1976. — Вып. 31. — С. 133-166.

61. Подколзин А. С. Об универсальных однородных структурах // Проблемы кибернетики. — М.: Наука, 1978. — Вып. 34. — С. 109-131.

62. Половников В. С. О некоторых характеристиках нейронных схем // Интеллектуальные системы. — 2004.— Т. 8, вып. 1-4. — С. 121-145.

63. Родин С. Б. Линейно реализуемые автоматы // Дискретная математика. — 2017. — Т. 29, № 1. — С. 59-79.

64. Саломаа А. Аксиоматизация алгебры событий, реализуемых логически-

ми сетями // Проблемы кибернетики. — М.: Наука, 1966. — Вып. 17. — С. 237-246.

65. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста / М.: Наука, 1966. — 120 с.

66. Часовских А. А. Об алгоритмической разрешимости проблемы полноты для линейных автоматов // Вестник Московского университета сер. 1, мат., мех. — 1986. — № 3. — С. 82-84.

67. Часовских А. А. О выразимости систем с сумматором в классе линейных автоматов // Вестник Московского университета сер. 1, мат., мех. — 1990. — № 4. — С. 31-34.

68. Часовских А. А. О полноте в классе линейных автоматов // Математические вопросы кибернетики. — 1991. — Вып. 3. — С. 140-166.

69. Часовских А. А. Замкнутые классы линейно-автоматных функций // Математические вопросы кибернетики. — 2004. — Вып. 13. — С. 113-136.

70. Часовских А. А. Об А-выразимости в классе линейно автоматных функций // Математические вопросы кибернетики. — 2008. — Вып. 17. — С. 105-136.

71. Часовских А. А. О проблеме полноты в классе линейно-автоматных функций над простыми конечными полями // в сборнике Материалы международной конференции «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика

B.А.Садовничего. — 2009. — С. 379-379.

72. Часовских А. А. О полноте в классе линейно-автоматных функций с операциями суперпозиции //в сборнике Материалы XI Международного семинара «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012 г.), 2012 — С. 382-385.

73. Часовских А. А. Линейно-автоматные функции с операциями суперпозиции // Нейрокомпьютеры: разработка, применение. — 2013. — № 8. —

C. 3-13.

74. Часовских А. А. О полноте в классе конечных автоматов, вычисляющих некоторые аффинные функции // Интеллектуальные системы. — 2013. — Т. 17, вып. 1-4. — С. 202-205.

75. Часовских А. А. Условия полноты линейно-р-автоматных функций // Интеллектуальные системы. Теория и приложения. — 2014. — Т. 18, вып. 3. — С. 203-252.

76. Часовских А. А. Проблема А-полноты линейно-автоматных функций над конечным полем // Интеллектуальные системы. Теория и приложения. — 2014. — Т. 18, вып. 1. — С. 253-257.

77. Часовских А. А. Проблема полноты для класса линейно-автоматных функций // Дискретная математика. — 2015. — Т. 27, № 2. — С. 134-151. Перевод: Chasovskikh A. A. Completeness problem for the class of linear automata functions // Discrete Mathematics and Applications. - 2016. - Vol. 26, Iss. 2. -Pp. 89-104.

78. Часовских А. А. Критериальные системы в классах линейно-автоматных функций над конечными полями // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, вып. 3. — С. 195-207.

79. Часовских А. А. Сравнение операторов замыкания в классе линейно-автоматных функций // Интеллектуальные системы. Теория и приложения. — 2016. — Т. 20, вып. 3. — С. 120-124.

80. Часовских А. А. О полноте в классе линейных 2-адических автоматов // Интеллектуальные системы. Теория и приложения. — 2016. — Т. 20, вып. 4. — С. 209-227.

81. Часовских А. А. Проблема полноты в классах линейных автоматов // Интеллектуальные системы. Теория и приложения. — 2018. — Т. 22, вып. 2. — С. 151-154.

82. Часовских А. А. Приведенные критериальные системы предполных классов в классах линейных автоматов над конечными полями // Интеллектуальные системы. Теория и приложения. — 2018. — Т. 22, вып. 4. — С. 115-134.

83. Часовских А. А. О числе максимальных надклассов в классе линейных автоматов // Интеллектуальные системы. Теория и приложения. — 2019. — Т. 23, вып. 3. — С. 81-84.

84. Часовских А. А. О классах передаточных функций линейных автоматов // Интеллектуальные системы. Теория и приложения. — 2019. — Т. 23, вып. 3. — С. 135-142.

85. Часовских А. А. О проблеме полноты в классах линейных автоматов над конечными полями //в сборнике Материалы XIII Международного семинара «Дискретная математика и ее приложения» (Москва, 17-22 июня 2019 г.), 2019 — С. 50-59.

86. Часовских А. А. Максимальные подклассы в классах линейных автоматов над конечными полями // Дискретная математика. — 2019. — Т. 31, № 4. — С. 88-101. Перевод: Chasovskikh A. A. Maximum subclasses in classes of linear automata over finite fields // Discrete Mathematics and Applications. - 2020. - Vol. 30, Iss. 6. - Pp. 365-374.

87. Часовских А. А. Классы линейных p-автоматов с операциями суперпозиции // Интеллектуальные системы. Теория и приложения. — 2021. — Т. 25, вып. 2. — С. 155-156.

88. Hensel K. Zahlentheorie / Berlin und Leipzig: G.m.b.H., 1913. — 449 p.

89. Budach L. Automata and labyrinth // Mathematische Nachrichten. — 1978. — Vol. 86. — P. 195-282.

90. Chung J., Gulcehre C., KyungHyun C., Yoshua B. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling // [Электронный ресурс]: Cornell University. URL: https://arxiv.org/pdf/1412.3555.pdf (дата обращения 05.01.2019).

91. Goto E. A Minimal Time Solution of the Firing Squad Problem // Dittoed course notes for Applied Mathematics, Harvard University 298. — 1962. — P. 52-59.

92. Hochreiter S., Schmidhuber J. Long Short-Term Memory // Neural

Computation. — 1997. — Vol. 9, № 8. P. 1735-1780.

93. Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities // Proceedings of National Academy of Sciences. — 1982. — Vol. 79, № 8. P. 2554-2558.

94. Lau D. Function Algebras on Finite Sets. A Basic Course on Many-Valued Logic and Clone Theory / Rostok: Springer, 2006. — 668 p.

95. Moore E. F. Machine models of self-reproduction // Math. Soc. Proc. of Symposia in Applied Mathematics. — 1962. — Vol. 14. — P. 17-33.

96. Myhill J. The converse of Moore's Garden-of-Eden theorem // Proc. Amer. Math. Soc. — 1963. — Vol. 14. — P. 685-686.

97. Post E. L. The two-valued iterative systems of mathematical logic //Annals of Mathematics studies / Princeton: Princeton University Press, 1941. — № 5, —122 p. Post E. L. Introduction to a General Theory of Elementary Propositions // American Journal of Mathematics. — 1921. — Vol. 43, No 3. — P. 163-185.

98. Rabin M. O. Probabilistic automata // Information and Control, — 1963. — Vol. 6, № 3. — P. 230-245.

99. Rosenberg I. G. The number of maximal closed classes in the set of functions over a finite domain // Journal of Combinatorial Theory, — 1973. — Vol. 14. — P. 1-7.

100. Streich W. J., Rosner Th. / Theorie linearer Automaten / Berlin.: VEB Deutscher Verlag der Wissenschaften, 1978. — 158 p.

101. Szendrei A. On closed classes of quasilinear functions // Chechoslovak Math. J. — 1980. — Vol. 30, No 3. — P. 498-509.

102. Von Neumann J. A., Burks W. Theory of Self-Reproducing Automata / Urbana, London: University of Illinois Press, 1966. — 388 p.