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

• Автор: Летуновский, Алексей Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 87 с. : ил.

Оглавление
Введение
1 Задача выразимости для произвольных систем автоматов
1.1 Задача выразимости константных автоматных функций
1.2 Достаточные условия конечности и бесконечности множества выразимых констант
2 Задача выразимости для расширенной суперпозиции. Цикловые индексы автомата.
2.1 Разрешимость задачи выразимости констант для расширенной суперпозиции
2.2 Цикловые индексы автомата
2.3 Задача выразимости автомата Zn
2.4 Задача выразимости линейных автоматов
3 Применение алгебраических конструкций в задаче выразимости автоматов относительно расширенной суперпозиции и Р'2 суперпозиции.
Литература
Публикации автора по теме диссертации

Введение
Общая характеристика работы
Актуальность темы исследования
Теория автоматов - раздел дискретной математики, возникший в середине 20-го века в связи с изучением свойств конечных автоматов. Конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной канал, конечное число состояний и в каждый дискретный момент времени, получая на вход один из конечного множества входных сигналов, осуществляющее изменение своего состояния, а также выдающее на выход один из конечного множества выходных сигналов. Автомат фактически производит отображение входных последовательностей в выходные. Связанное с автоматом отображение называется автоматной функцией. Возможность получения новых автоматных функций за счет соединения автоматов приводит к алгебре автоматных функций.
Первой работой, давшей толчок к развитию теории автоматов, является работа Э. Поста 1941 года[1]. В ней была описана структура решетки замкнутых классов булевых функций. Булевы функции являются частным случаем автоматов - автоматами без памяти. Сами автоматы и их алгебры начали исследоваться в тридцатые годы предыдущего столетия, но особенно активно в период 50-х годов.
Возникшие для булевых функций, а также для функции к-значной логики, задачи о выразимости, полноте, базисах актуальны и для автоматных функций. Применим к ним и ап-

парат, используемый для решения этих задач. Под выразимостью здесь понимается возможность получения одной автоматной функций через другие автоматные функции. Частным случаем задачи выразимости является задача полноты, в которой проверяется возможность выразимости всех автоматных функций.
Теория автоматов наиболее тесно связана с теорией алгоритмов - наукой, возникшей в 30-х годах прошлого столетия в связи с возникновением предположений о невозможности алгоритмического разрешения многих математических проблем (в частности проблема соответствия Поста[2]).
Алгоритмические задачи в теории автоматов возникли в 1960-х годах в связи с проблемой разпознавания полноты: требуется найти алгоритм, позволяющий по любому заданному базису установить, является ли он полным или нет. Для некоторых классов автоматов эта задача была решена.
Э.Пост и С.В. Яблонский решили данную задачу для автоматов без памяти[1, 3], В.Б. Кудрявцев установил критерии полноты для функций с задержками[4], A.A. Летичевским были сформулированы условия полноты для базисов, содержащих автоматы Медведева и автоматы без памяти[5]. Вместе с тем В.Б. Кудрявцев показал континуальность множества предполпых классов автоматных функций[6], а М.И. Кратко доказал алгоритмическую неразрешимость в общем случае проблемы распознавания полноты для конечных автоматов относительно операции суперпозиции и обратной связи[7]. В последней работе фактически была доказана алгоритмическая неразрешимость проблемы выразимости константных автоматов относительно операции суперпозиции.
В дальнейшем задача полноты для автоматных функции широко изучалась в различных вариациях. При этом применялись несколько подходов.
Первый подход связан с вариацией понятия равенства ав-

При И = О получаем, что Н(0,0,0) = 0 , при И = р получаем, ЧТО /г(р,р, ..-,Р) = Р■ ПреДПОЛОЖИМ, ЧТО Н(Х1,Х2, ...,хт) = хт+1 существенно зависит от яд, тогда найдутся наборы (а, с2, сг), (Ь, с2,.... ст), такие что
М+ сь ..., сф) = сф <1 = к(Ь, с2,..., (+).
Для функции
= Уфк(а, с2,..., сг), /1(6, с2,..., Сг)) = По (с, г!) = 1.
Если предположить, что Мжъ х2, ■■■, хт) = хт+1 зависит существенно от двух переменных, то получим, без ограничения общности
Если далее взять ИДзду) = тах(х, у), И2(а:, у) = а: + у, то получим противоречивые равенства:
Следовательно Н{х)Х2, ..., я+) = хт+ функция одного переменного, сохраняющая все константы, то есть к(хь ж2,..., хт) — ад при некотором г, что означает неотличимость моментов времени г и т+1 и противоречит условию леммы. Значит |Ь(Л)]т+1| > 2Г и найдутся наборы (щ, с2,..., сг, с), (щ, с2,..., сг, в) £ Ь(П)]г+1 из которых с помощью функции По можно получить набор (0,0,.... 1) длины т + 1, складывая который с другими наборами получим все наборы длины т + 1. Ь(А)]т+ = /Д+1. Лемма 1.8 доказана.
Доказательство леммы 1.9.
соотношение 1.2 даст
/1(1,0,.., .0) = Л(Ио(а, Ь), По(с2, с2),..., И0(сг, ст)) =
Л(1,0,0) = 1, Л(0,1,0, 0) =
Л(1,1,0,..., 0) - МИД1,0), ИДО,1), ИДО, 0),..., ИДО,0) =
= ИДМД0,..., 0), МО, 1, о,.., 0)) == ИД1,1) =
*(1,1,0,..., 0) = МИД1,0), ИДО, 1), И2(0, 0),..., ИДО, 0)) -
= идмп о,..., 0), МО, 1, о,..., 0)) = ИД1,1) = о