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

Введение

Глава I. Универсальные автоматы

1.1. Универсальность в классах конечных автоматов

1.2. Полнота и анализ универсальных автоматов

Глава 2. Характеризация универсальных автоматов отношением

2.1. 6- эквивалентность в симметрической полугруппе преобразований

2.2. Эквивалентность графов преобразований

2.3. Рекуррентный синтез -различных преобразований симметрической;полугруппы

2.4. Приближенные оценки индекса отношения 8

- симметрической полугруппы преобразований

2.5. Характеризация универсальных автоматов отношением

Глава 3. Применение модели универсального автомата для решения задач технической диагностики

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

3.2. Использование модели универсального автомата и метода квазиуниверсальных тестов для построения схем встроенного контроля

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

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

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

Первый из них связан с понятием функциональной полноты и однородной структуры. В 1956 году Минский в работе [ I ] поставил задачу о построении универсального автомата как базового объекта для создания некой однородной структуры, реализующей поведение любого из заданного множества элементов. В 1960 году в 3 впервые дано формальное определение универсального обьекта как математической модели, образующей функционально полную систему, решил задачу построения и определения основных свойств универсальной о-д. функции. Затем [8 J строится пример универсальной о-д. функции с двумя входными каналами и двумя состояниями. В этом случае, для моделирования закона функционирования любого автомата необходимо каждый раз построение специальной автоматной схемы.

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

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

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

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

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

В [7] предложил метод построения универсальной и многофункциональной /универсальной для некоторого конечного множества/ булевых функций. Возможность получения всех настроек параллельно с определением универсальной функции является отличительной особенностью и несомненным преимуществом данного метода среди подобных работ Для некоторых классов конечных автоматов задача универсализации рассматривалась в работах , . Их исследования были посвящены изучению поведения развивающихся оценок функции роста. Базовым элементом при построении моделей систем такого рода являлся так называемый автомат локального действия /а.л.д./. Было доказано, что а.л.д. есть универсальный автомат для определенного класса. Универсальность а.л.д. достигалась путем изменения структуры в процессе функционирования при подаче некоторой метакоманды К. Таким образом, универсальность в данном случае есть возможность моделировать работу произвольного объекта за счет изменения каждый раз определенной структуры, что вообще говоря, является некоторой интерпретацией концепции универсальности Минского-Кудрявцева.

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

Во-первых,проблема получения адекватного математического описания является традиционно актуальной как при проектировании, так и при диагностировании сложных технических систем. Универсализация элементной базы, широкое использование объектов с перенастраивав -мым законом функционирования настоятельно требует создания математических моделей для их полного описания. Для комбинационных схем эта задача успешно была решена в работах |?,9,22| созданием универсальных и многофункциональных логических модулей, реализующих соответственно или все булевые функции или только их некоторый класс. Однако, для более интересного как с практической, так и с теоретической точки зрения класса, каким являются схемы с памятью, в общем случае, вопрос о существовании и методах построения аналогичных классов моделей остается открытым.

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

- построение универсальных методов контроля и диагностирования;

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

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

Методологическую основу работы составляют теоретико-автомат -ные, алгебраические и комбинаторно-логические методы. Их использование позволило определить способы построения для произвольного класса | соответствующего универсального автомата , изучить взаимосвязь понятия "универсальность" в смысле концепций Минского--Кудрявцева и Шеннона на множестве конечных детерминированных автоматов. Следовательно, в диссертации получено решение как ряда новых задач, так и ранее изучавшихся проблем, связанных со свойством универсализации.

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

ЗАКЛЮЧЕНИЕ.

Основным результатом диссертации является характеризация свойства "универсальности" конечных автоматов; построение метода, определяющего для произвольного класса универсальный и сильно универсальный автоматы; доказательство совпадений концепций "универсаль -ности" Минского-Кудрявцева и Шеннона на множестве конечных детерми -нированных автоматов; исследование свойств универсального автомата -- полноты, анализа, рекуррентного синтеза, асимптотического поведе -ния последовательности универсальных автоматов; изучение возможных прикладных приложений универсального автомата как математической модели перенастраиваемых технических систем. Перечислим полученные в этом плане результаты диссертации.

1. Определен метод построения универсального и сильно универсального автомата минимального в смысле отношения предшествования для класса (п, г) при произвольном натуральном П . Функция переходов такого автомата есть объединение всех представителей классов

Е - эквивалентности симметрической полугруппы преобразований в^. Функция выходов - многофункциональный комбинационный модуль.

2. Найден критерий решения задачи анализа произвольного универсального автомата. Показано, что решением задачи анализа является множество автоматов, пересечение (Х,£) гомоморфных образов которых содержит заданный универсальный автомат.

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

4. Показана алгоритмическая неразрешимость в общем случае задачи рекуррентного синтеза. В то же время, для множества минимальных универсальных автоматов п-1 J при произвольном п определен метод построения универсального автомата для класса (Г), <?) путем рассмотрения процесса порождения £ - различных пре -образований полугруппы из £ - различных преобразований полугруппы СтпЧ .

5. С целью изучения асимптотического поведения последователь -ности универсальных автоматов {5с)п определен индекс отношения £ в симметрической полугруппы преобразований как функ -ции от п и строения произвольного класса £ - эквивалентности. Показано, что рост этой функции близок к экспоненциальному.

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

Результаты пунктов I и 3 показывают, что предложенная модель универсального автомата позволяет доказать совпадение концепций Минского-Кудрявцева и Шеннона на множестве конечных автоматов. В то же время, результаты пункта 2 позволяют определить ряд новых свойств универсальных моделей Кудрявцева и Шеннона с точки зрения ( X,Ь) гомоморфизма. Эти теоретические результаты могут быть полезны при изучении свойств универсальности для более мощных классов моделей / 5 - автоматов, МП - автоматов,

АО

- автоматов/. Также важным, но уже в прикладном плане, являются утверждения пунктов 5и 6, поз

- из воляющие получать и оценивать основные характеристики универсальных автоматов при произвольном натуральном П .

Автор считает своим искренним долгом выразить глубокую благодарность научному руководителю, профессору А.М.Богомолову за постановку задачи, за многолетнюю и многостороннюю помощь.

1. Автоматы. Сб.статей под редакцией Шеннона. М., "Иностранная литература", 1956, 163-178 с.

2. Барздинь Я.М. О проблеме универсальности в теории автоматов. Дис.канд., Новосибирск, 1965.

3. Барздинь Я.М., Калниньш Я.Я. Универсальный автомат с переменной структурой. "Автоматика и вычислительная техника", №2, 1974.

4. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразование дискретных автоматов. Киев. "Наукова Думка", 1975.

5. Богомолов A.M.', Сытник A.A. Классы £ эквивалентности полугруппы преобразований конечного детерминированного автомата. В кн.; "Методы и системы технической диагностики", №3, Изд-во Сарат. ун-та, 1984, 3-12 с.

6. Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем. Киев, "Наукова Думка", 1974.

7. Богомолов A.M., Твердохлебов B.I. Целенаправленное поведение автоматов. Киев, "Наукова Думка", 1975.

8. Буевич В.А. Построение универсальной о-д. Функции с двумя переменными. "Проблемы кибернетики", №15, 1965, 249-252 с.

9. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с наст -раиваемой структурой. М., "Энергия", 1974.

10. Кротко М.й. Алгоритмическая неразрешимость одной задачи из теории конечных автоматов. В кн.:"Дискретный анализ", №2, Новоси -бирск, 1964.

11. Кудрявцев В.Б. Вопросы полноты для систем автоматов. ДАН СССР 130, 6, I960, II9I-II92 с.

12. Кудрявцев В.Б., Алешин С.В., Поколзин A.C. Элементы теории автоматов. М., Изд-во МГУ, 1978.

13. Мищенко В.А., Козюминский В.Д., Семашко А.Н. Многофункциональные автоматы и база цифровых ЭВМ. М., "Радио и связь", 1981.

14. Риордан Дж. Введение в комбинаторный анализ. М., "Иностранная литература", 1963.

15. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М., "Наука", 1982.

16. Сытник A.A. Об одном методе минимизации решений задачиуправления автоматов. В кн.¡"Методы и системы технической диагнос-«тики", №2, Изд-во Сарат. ун-та, 1982, II-I4 с.

17. Сытник A.A. Структурно-функциональный метод построения квазиуниверсальных тестов. В кн.:"Методы и системы управления и диагностирования. Изд-во Сарат. ун-та, 1984, 65-69 с.

18. Сытник A.A., Синельникова Н.Д. Оценка длины эксперимента по распознаванию конечного детерминированного автомата произвольного типа. В кн.:"Методы синтеза и планирования развития структур сложных систем". Изд-во Сарат. ун-та, 1980, 80-81 с.

19. Твердохлебов В.А. Универсальное решение задачи распознавания автоматов. В кн.:"Методы и системы технической диагностики". №2, Изд-во Сарат. ун-та, 1981, 3-6 с.

20. Эдрюс Г. Теория разбиений. М., "Наука", 1982, 80-87 с.

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

22. Якубайтис Э.А. Логические автоматы и микромодули. Рига, "Зинатне", 1975.