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

ФГБОУ ВО Московский государственный университет им. М.В. Ломоносова

Летуновский Алексей Александрович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

1 2 О 2015

город Москва — 2015

005558821

005558821

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова».

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Бабин Дмитрий Николаевич

доктор технических наук, профессор Фролов Александр Борисович ФГБОУ ВПО Национальный исследовательский университет «Московский энергетический институт», Институт автоматики и вычислительной техники, профессор кафедры Математического моделирования, кандидат физико-математических наук, доцент Мастихина Анна Антоновна ФГБОУ ВПО Московский государственный технический университет им. Н.Э.Баумана, доцент кафедры Высшей математики

ФГБОУ ВПО «Московский государственный университет приборостроения и информатики»

Защита состоится 27 февраля 201ог в 16:45 на заседании диссертационного совета Д.501.001.84 на базе ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова», по адресу: 119991, Москва, ГСП - 1, Ленинские горы, д.1, ФГБОУ ВО МГУ имени М.В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова» (Москва, Лпчпнпгпвлкий проспект, д.27, сс!чшр А, 8 этчиО../? Ь >"*• }>■ . ¡1/. 5 Ь)

Автореферат разослан 26 января 2015г.

Ученый секретарь диссертационного совета Д.501.001.84 на базе ФГБОУ ВО МГУ, д.ф.-м.н.

Иванов Александр Олегович

Общая характеристика работы Актуальность темы

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

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

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

Теория автоматов наиболее тесно связана с теорией алгоритмов - наукой, возникшей в 30-х годах прошлого столетия в связи

'Post Е. Two-Valued l.erative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941

с возникновением предположений о невозможности алгоритмического разрешения многих математических проблем (в частности проблема соответствия Поста2).

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

Э.Пост и C.B. Яблонский решили данную задачу для автоматов без памяти3,4, В,Б. Кудрявцев установил критерии полноты для функций с задержками5, A.A. Летичевским были сформулированы условия полноты для базисов, содержащих автоматы Медведева и автоматы без памяти6. Вместе с тем В.Б. Кудрявцев показал континуальность множества предиолиых классов автоматных функций7, а М.И. Кратко доказал алгоритмическую неразрешимость в общем случае проблемы распознавания полноты для конечных автоматов относительно операции суперпозиции и обратной связи8. В последней работе фактически была доказана алгоритмическая неразрешимость проблемы выразимости константных автоматов относительно операции суперпозиции.

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

Первый подход связан с вариацией понятия равенства автома-

2Post Е. A variant of recursively unsolvable problem, Bull. Amer. Math. Soc 52. 194G

3Post E. Two-Valued l.erative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941

4Яблонский C.B. Функциональные построения в ^-значной логике, Труды математического института им. В.А. Стеклова, АН СССР, 1958, Т.51, сгр. 5-142

''Кудрявцев В.Б. Теорема полноты для одного класса автоматов без обратных связей. Проблемы кибернетики, 1962 год №8, стр. 01-115

°Летичевский A.A. Условия пол»«™ для конечных автоматов, Вычислительная математика и математическая фц=лка, №4, 1961 год, стр. 702-710.

7Кудрявцев В.Б. О мощностях множеств предполных классов некоторых функциональных систем, связялных с автоматами, ДАН СССР т.151,N3,1963, с.493-496.

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

тов. При этом использовались такие понятия равенства, как А-полнота. (В.А. Буевич 9,10), Клини-иолнота (J. Dassow п), е-иолнота (Строгалов А.С.12 ), полнота с учетом недостижимых состояний (Хабзун И.В.13), N - полнота (Бабин Д.Н.14). Все эти задачи оказались алгоритмически неразрешимыми.

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

Третий подход связан с ограничениями на исследуемые системы автоматов. А.А. Летичевский нашел алгоритм решения задачи о полноте относительно композиции для конечных систем автоматных функций, выдающих свое состояние (автоматов Медведева) при наличии всех булевых функций17. В 1986 В.А. Буевич показал алгоритмическую разрешимость задачи А-полноты для систем, содержащих все булевы функции18. В 1992г. Д.Н. Бабин показал существование алгоритма распознавания полноты относительно суперпозиции и обратной связи для систем, содержащих все булевы"

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

10Буевич В.А. Условия А-полноты для автоматов, M., изд. МГУ, 1986

"Dassow J., Ein modifizierter Vollstandigkeitsbegriff in einer Algebra von Automatenabbildungen, Dissertation Doktor B, Rostock, Universitet,1978.

12Строгалов A.C., Метрические свойства о.д.-функцнП. Межвузовский сборник трудов, N 50, МЭИ, 1985, стр. 80-84

"Хазбун И.В., Об условиях полноты и выразимости в точной алгебре автоматов, Логико-алгебраические конструкции, Тверь 1984, стр. 35-41.

14Бабин Д.Н. О суперпозициях о.д.-функцпй ограниченного веса, Логико-алгебрапческне конструкции, Тверь 1D84, стр. 21-27

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

10Часовских А.А., О полпоте в классе линейных автоматов, Математические вопросы кибернетики, 1995, N3, стр. 140-1С6.

17Летичевский А.А. Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, №4, 1961 год, стр. 702-710.

|8Буевпч В.А. Условия А-полноты для автоматов, М., изд. МГУ, 19S6

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

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

Вместе с тем, после работы М.И. Кратко22 задача алгоритмической разрешимости для выразимости автоматов широко не изучалась. Основные работы но этой теме были посвящены алгебраической теории автоматов, которая развивалась за рубежом в 1970-х годах и связана в основном с работами К. Крона и Дж. Роудза. Теорема Крона-Роудза фактически утверждает, что любой автомат можно получить суперпозициями триггеров и автоматов, полугруппы которых являются простыми группами, содержащимися в полугруппе первоначального автомата23.

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

10 Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, стр. 41-56, Наука, Москва

20Бабин Д.Н., О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты, ДОКЛАДЫ АКАДЕМИИ НАУК, N 4, Т.367, 1999 стр. 439-441

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

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

23Арбиб М, Алгебраическая теория автоматов языков и полугрупп, "СтатистикаМ.,1975

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

C.B. Алешин показал, что в теореме Крона-Роудза при наличии в базисе константных автоматов может быть снято ограничение на специальный вид групповых автоматов в композиции. C.B. Алешин показал, что для любой простой группы G достаточно взять любой групповой автомат, группа которого имеет G в качестве делителя24. Тем не менее, вопрос алгоритмической неразрешимости задачи выразимости остался открытым. Цель работы

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

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

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

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

• Введено понятие расширенной суперпозиции

24 Алешин C.B., Об одном следствии теоремы Крона-Роудза, Дискретная математика, том 11, пып.4, 1999 год, стр. 101-109

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

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

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

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

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

• Доказана алгоритмическая разрешимость и приведен критерий выразимости групповых автоматов для систем с фиксированной добавкой - штрих Шеффера и - универсальный

. автомат с 2-мя состояниями.

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

Основные методы исследования

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

Теоретическая и практическая значимость

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

Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах: кафедральный семинар 'Теория автоматов" кафедры Математической Теории Интеллектуальных Систем МГУ под руководством академика В.Б. Кудрявцева (20052014гг, неоднократно), "Теория дискретных функций и приложения" под руководством Д.Н. Бабина (2004-2014гг, неоднократно), "Дискретный анализ" под руководством C.B. Алешина (2005-2013гг, неоднократно)

Также результаты докладывались на следующих международных конференциях

• IX международная конференция "Интеллектуальные системы и компьютерные науки" (Москва, 23-27 октября 2006г)

• X международная конференция "Интеллектуальные системы и компьютерные науки "(Москва, 5-10 декабря 2011г)

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

• XVII Международная конференция "Проблемы теоретической кибернетики"(Казань, 16-20 июня 2014г)

Структура диссертации

Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы, содержащего 34 наименований. Общий объем диссертации 87 страниц. Публикации

Результаты диссертации опубликованы в 7 работах автора. Краткое содержание работы

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

Глава 1 посвящена введению основных понятий функциональной системы автоматных функций а также изучению алгоритмической разрешимости задачи выразимости относительно выразимости и А-выразимости для произвольных систем автоматов: Определение 1.1 Пусть п,т £ N

/ : {Е?)п -»■ (.Е?)т

- автоматная функция( а-функция), если она задается рекуррент-но соотношениями

' 5i(l) = gOb

qs( 1) = qOs

qi(t +1) = Qs(t), ab..., a„),

...

q$(t + 1) = <f>s{q i(i),..., qa(t), ah..., an) h{t) = 4>i(qi(t),..., qs(t), au ..., a„)

. bm(t) = ipm{qi(t),..., q3(t), ab ..., an)

Вектор q = (<7i, ■■■,qs) задает состояние a-функции /, qO ее начальное состояние, буквы а = (aio2...an) и b = (i>i...bm) называются входной и выходной буквами, а сверхслова a(l)a(2)... и 6(1)6(2)... - входными и выходными сверхсловами, соответственно. Вектор-функции ф и гр называются функциями переходов и выходной функцией, соответственно Определение 1.2 Шестерка

(Щ,Е%,Е?,ф,ф,д 0)

- называется автоматом, порождающиль функцию /.

Автомат называется автоматом Медведева, если В = Q,i>(a.q) = q.

Класс всех автоматных функций обозначим через Р.

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

Пусть AI С Р, обозначим через [AI] - множество а-функций, получающихся из AI с помощью операций суперпозиции.

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

Определение 1.3 Пусть М е Р. Обозначим < AI >= [М U {Рг, С?о}], здесь Gq - автомат "задержки"с нулевым начальным состоянием, Рг множество всех булевых функций. Будем называть < AI > замыканием М относительно расширенной суперпозиции.

Заметим, что P-z порождается универсальной функцией "штрих Шефферапоэтому добавку {P2,Gq} можно считать конечной

Определение 1.4 Пусть т € N.f - некоторая автоматная функция, обозначим через

Г : (ЩТ {Щ)'п

ограничение этой функции на множество слов длины т. Скажем, что а - функции /(xj, ...,£„) и <7(2:1, .-..а:,,.) - т - равны, если /т = дт. Обозначим через [М]т - множество всех о-функций, т- равных получающимся из AI с помощью суперпозиции, пусть

оо

№а = П №г,

т=1

назовем [А1]л - А- замыканием множества AI.

Определение 1.5 Автоматная функция к - называется кон-стпантпной,если для любого входного сверхслова а(1)а(2)... ее выходное сверхслово - это одно и то же периодическое сверхслово

/с(а(1)а(2)...) = 6(1)6(2)... = ß

В главе 1 в новых обозначениях были передоказаны следующие теоремы:

Теорема 1.1 Кратко 25 Задача выразимости констант алгоритмически неразрешима.

Теорема 1.2 Буевич26 Задача А-выразимости констант алгоритмически неразрешима.

А также доказаны следующие теоремы

Теорема 1.3 Задача пустоты множества выразимых констант алгоритмически неразрешима.

Теорема 1.4 Задача пустоты множества А - выразимых констант, алгоритмически неразрешима.

Теорема 1.5 Задача бесконечности множества выразимых констант, алгоритмически неразрешима.

Теорема 1.6 Задача бесконечности множества А - выразимых констант, алгоритмически неразрешима.

Также в главе 1 приведены достаточные условия конечности и бесконечности множества выразимых констант:

Для автоматной функции А определим последовательность подмножеств состояний:

Qo = quQi = {0(gi,a)|a е Щ}.....Qi+1 = {<?%,а)|д; Е Qua е

Щ}-

Это периодическая последовательность, пусть d - ее иредпериод, а Ра - период, г = Q(A) - число состояний автомата А, тогда ро < 2Г, d < 2Г.

Для г ф j через Kjj с К обозначим подмножество сверхслов a(l)a(2)..., у которых а (г) = a(j). Скажем, что автоматная функция А сохраняет множество Кц, если А(К^) С Kih в противном случае будем говорить, что автомат отличает моменты времени г

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

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

И 3-

Имеет место теорема 1.7 о необходимом условии конечности множества выразимых констант

Теорема 1.7 Пусть для некоторых г,] < р{А), в = j ■ ¡ф(Л)|, А сохраняет множества £ = О,.., в,

тогда \[А и Р2] Л К\ < оо.

Теорема 1.8 дает достаточные условия бесконечности множества выразимых констант.

Теорема 1.8 Пусть для всех г, у < р(А), г Ф ], А отличает моменты времени г пЗ, тогда |[ЛиРг]ЛАг| = оо и ¡[ЛиРгЦЛК"! = оо

В Главе 2 вводится понятия:

Автономной назовём автоматную функцию с безусловными переходами. Класс автономных автоматных функций обозначим через V. Заметим, что К с V.

Определение 2.1 Пусть сверхслово 0 можно представить в виде Р — 70.'°°. Выберем из всех таких представлений такое, что 7 и а имеют наименьшую длину. Для выбранного представления назовем 7 - наименьшим предпериодом сверхслова /3, а а наименьшим периодом сверхслова /3, а слова вида (т^а, будем называть

п

периодом сверхслова здесь п 6 N. Обозначим |«| длину слова а.

Для множества константных автоматных функций К' С К обозначим через 0(Л"')- множество длин минимальных периодов сверхслов : К{ € К'}.

В параграфе 1 главы 2 рассматриваются следующие задачи: по конечному множеству автоматов М С Р и /3 € К проверить, верно ли что

1)0 е< М > 2)| 6(< М > ПК) |< оо 3)Описать множество 0(< М > С\К). Также определяются цикловые индексы автомата через алгоритм их вычисления

Для некоторого автомата М и произвольного слова аеЛ* обозначим через за = ф(д. а) - подстановку на множестве состояний, задаваемую этим словом, жа - разбиение множества состояний <3 на классы отличимости <31,...<38 этим словом. Состояния д; и д,-принадлежат одному классу отличимости, если а) = ф^, а).

Обозначим еа = (йа,7га). Пусть = {еа, |а| = /}.

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

Пусть Сг = {а;} - множество сверхслов с длиной периода 1\щ. Рассмотрим множество - М(с() выходных сверхслов автомата М после подачи на него сверхслов из с* . Очевидно, что 0(М(с;)) -конечно. Тогда положим щ+х = #£Ж(0(М(с,;))). щ - максимальная длина периода констант, выразимых схемой глубины г, если не учитывать в схеме автоматы без памяти.

1. Вычисляем последовательность (гг,, до тех пор, пока не найдутся j < г, такие, что Ещ = Еп .

2. Назовем 6 = п^ - безусловным цикловым индексом автомата,

а = г1- - главным цикловым индексом автомата.

'Ъ

Верны следующие теоремы

Теорема 2.2 Пусть М - автоматная функция, тогда 9(< М > ПК) = Ц™1{1|« делит &51}, где - цикловые индексы автомата М.

Из теоремы 2.2 следует

Теорема 2.3 Пусть М € Р и Р 6 К, тогда существует алгоритм, позволяющий проверить свойство ¡3 е< М >.

и

Следствие 2.2 Пусть М - автоматная функция и у - автономная автоматная функция, тогда существует алгоритм, позволяющий проверить свойство у £< М >

В параграфе 2 главы 2 приведены примеры вычисления цикловых индексов автомата, а также приведены оценки сложности их вычисления.

В параграфе 3 главы 2 введено понятие автомата Zn Определение 2.2 Автоматом Zn, п £ N будем называть автомат Медведева вида

({0,1},{1....,гг},{1.....п},ф,1>, 1)

ф{г, 1) = г, ф^, 0) = (г + 1) mod п ip(i, 0) = ф(г, 1) = г.

Для выразимости данного автомата верны следующие теоремы: Теорема 2.6 Пусть М £ Р, тогда Zn выразим через

< М > тогда и только тогда, когда п делит некоторую степень главного циклового индекса М.

Теорема 2.7 Пусть М б Р, тогда существует алгоритм, позволяющий проверить свойство выразимости Zn через

< М >.

Автомат L = (Е^, Q, El2^,ip,qO),Q С Е%, называется линейным, если

ф(х,(]) = Aq + Вх, ф(х, q) = Cq + Dx, go = (0,0,..., 0),

где Л : ££ Щ, В : Е%, С : -4 El2, DB : -> Е12 - есть линейные операторы. Матрица А называется основной матрицей линейного автомата.

Доказаны следующие теоремы: Теорема 2.8 Пусть М £ Р , a L - линейный автомат, тогда

L е< М >о ©(< L > ПК) С е(< М > ПК)

То есть для выразимости линейного автомата необходимо и достаточно выразить все через него выразимые константы.

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

В Главе 3 рассматривается применение алгебраических конструкций в задаче выразимости автоматов

Определение 3.1 Пусть М = (A,Q, B,(f>,w,qo) - конечный автомат. Множество подстановок {фа : Q —> Q\a £ А}, где фа(я) — ф(д, а), порождает полугруппу подстановок S на множестве Q. Изоморфную S абстрактную полугруппу будем называть полугруппой автомата М и обозначать Sm-

Автомат называется групповым, если его полугруппа является группой.

В главе 3 доказаны следующие теоремы:

Теорема 3.4 Пусть М 6 Р , G - произвольный групповой автомат Медведева, тогда проверка G £< М > алгоритмически разрешима-

Автоматную функцию F2, задаваемую уравнениями <7(1)= О,

q{t + l) = q{t)a1{l)Vq{t)ai{t), b(t) = q{t),

назовём универсальной автоматной функцией с 2-мя состояниями.

Обозначим < М >р2= [М U {F2, Р2}}.

Теорема 3.5 Пусть М е Р , G - произвольный групповой автомат, тогда G £< М >р2 алгоритмически разрешима.

Теорема 3.6 Пусть М 6 Р, Рп - все автоматы с не более, чем п состояниями. Тогда задача < М Рп является алгоритми-

чески разрешимой.

Заключение

Основными результатами работы являются:

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

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

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

4. Введение понятия циклового индекса автомата и применение его для решения задачи выразимости автоматов.

5. Описание множества всех выразимых через автомат константных автоматных функций.

Благодарность

Автор выражает глубокую благодарность своему научному руководителю - доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задачи, постоянное внимание к работе и всестороннюю поддержку, а также заведующему кафедрой, академику В.Б. Кудрявцеву и всему коллективу кафедры Математической Теории Интеллектуальных Систем за доброжелательную и творческую атмосферу.

Список работ автора по теме диссертации

[1] A.A. Летуновский. О выразимости константных автоматов. Интеллектуальные системы, т.9, вып.1-4, 2005, с.457-469.

[2] A.A. Летуновский. О выразимости константных автоматов суперпозициями. Интеллектуальные системы, т.13, вып.1-4,2009, с.397-406.

[3] A.A. Летуновский. О выразимости суперпозициями автоматов с' разрешимыми группами. Интеллектуальные системы, т. 14, вын.1-4, 2010, с.379-393.

[4j A.A. Летуновский. О задаче выразимости автоматов относительно суперпозиции для систем с фиксированной добавкой. Интеллектуальные системы, т. 15, вып. 1-4, 2011, с.401-412.

[5] A.A. Летуновский. О задаче выразимости автоматов относительно суперпозиции для систем с фиксированной добавкой. Интеллектуальные системы в производстве, №1, 2012, с.36-50.

[6] A.A. Летуновский. О выразимости суперпозициями групповых автоматов Медведева. Интеллектуальные системы, , т.17, вып.1-4, 2013, 179 181.

[7] A.A. Летуновский. Цикловые индексы автомата. Дискретная математика, т.25, выи.4, 2013, с.24-29.

Отпечатано в отделе оперативной печати Геологического ф-таМГУ Тираж 1С 0 экз. Заказ № í