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

Введение

1. Свойства отображений, непредставимых специальными классами конечных детерминированных автоматов

1.1. Основные понятия и определения

1.2. Построение иерархии классов конечных детерминированных автоматов.

1.3. Необходимое и достаточное условие отделимости классов конечных автоматов

1.4. Виды нереализуемых отображений

1.4.1. Нереализуемые связи для однородных входных последовательностей

1.4.2. Нереализуемые связи между периодическими и квазипериодическими входными последовательностями и выходными последовательностями

1.4.3. Использование универсальных тестов

2. Свойства геометрических образов автоматов и классов автоматов

2.1. Словарная геометрия и построение геометрических образов автоматов

2.2. Преобразование образа при изменении порядка в пространстве

2.3. Закон изменения мощностных характеристик образа при переходе от клетке к клетке

2.4. Геометрическое условие неавтоматности

3. Свойства линейных последовательностных машин и их отображений

3.1. Основные понятия и определения

3.2. Место классов линейных последовательностных машин в иерархии классов конечных детерминированных автоматов

3.2.1. Перечисление конечных детерминированных автоматов

3.2.2. Перечисление линейных последовательностных машин

3.3. Место классов билинейных систем в иерархии классов конечных детерминированных автоматов

3.4. Непредставимые отдельными классами ЛПМ отображения

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

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

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

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

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

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

Для достижения указанной цели были поставлены задачи

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

- нахождения необходимых и достаточных условий выделения некоторых классов конечных детерминированных автоматов по непредставимым ими отношениям,

- построения эффективных критериев определения непредставимых линейными и билинейными автоматами вход-выходных связей,

- определения места класса линейных последовательностных машин и билинейных систем в иерархии конечных автоматов.

Относительно этих вопросов можно отметить следующие полученные результаты. Некоторые аналитические описания недопустимых вход-выходных зависимостей были получены в работах Минского, Хомского, К лини, Гилла и Глушкова и др.

- В монографии H.Minsky "Computation:Finite and Infinite Machines" приведена

Теорема 1. He существует конечного автомата Мили, способного перемножать сколь угодно длинные (большие) двоичные числа.

- Н.Хомским [41] была доказана

Теорема 2. Не существует конечного автомата, способного проверить симметрию входного слова.

- С. К лини показал в статье "Представление событий в нервных сетях и конечных автоматах" [9], что справедлива

Теорема 3. Непредставимо в качестве регулярного события событие S, состоящее из всех слов в непустом конечном алфавите X, длины которых являются точными квадратами.

- в монографии В.М.Глушкова "Синтез цифровых автоматов" доказана

Теорема 4. Если событие S представлено в конечном автомате Мили или Мура с п состояниями множеством выходных сигналов (или множеством внутренних состояний), то это событие регулярно и допускает регулярное выражение, циклическая глубина которого не превосходит п.

- в монографии А.Гилла "Линейные последовательностные машины" доказана

Теорема 5. Пусть автономная последовательностная машина (АЛПМ) Л имеет многочлен обратной связи ф{х) = «о + а\х + ■ • • + ап-1хП~1 + хП Последовательность

У{*) ■ У0У1У2 ■ ■ ■ над полем GF(p) является выходной последовательностью АЛПМ Л тогда и только тогда, когда для всех t ^ О yt+n = -a0yt - axyt+1-----<^п-1Ш+п-1 •

Вновь полученными результатами по теме диссертации являются

- найден эффективный критерий решения задачи выделения класса конечных детерминированных автоматов с заданным объемом памяти;

- найден и обоснован метод выделения класса конечных детерминированных автоматов с заданным объемом памяти, который позволяет по результатам кратного условного эксперимента над классом инициальных конечных детерминированных автоматов с неизвестным объемом памяти, определить этот объем;

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

- получено геометрическое условие неавтоматности фигуры геометрии Го;

- построено перечисление (в смысле А.Гилла) классов линейных последовательностных машин и билинейных систем, их специальных подклассов, в частности явносократимых, минимальных и неизоморфных линейных последовательностных машин и билинейных систем;

- определено место классов линейных последовательностных машин и билинейных систем в иерархии классов конечных детерминированных автоматов;

- найдены вход-выходные зависимости, нереализуемые частными классами линейных последовательностных машин (классами с ограничениями на характеристическую матрицу А, матрицы В, С, D).

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

Диссертация выполнена в течении 1992-2001 г.г., тема диссертации утверждена на заседании ученого совета университета (протокол № 9 от 20 мая 1999г.).

Основные результаты получены автором самостоятельно и обсуждались с научным руководителем.

Результаты работы докладывались и обсуждались на IX Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996), на международной научной конференции "Аналитическая теория автоматического управления и ее приложения" (Саратов, 2000г), конференции сотрудников механико-математического факультета СГУ, посвященной 90-летию университета (Саратов, 1999), семинарах в Саратовском государственном университете.

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

Заключение

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

1. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. М.:Наука.-1963.

2. Батраева И.А. Нереализуемые автоматами связи между периодическими входными и выходными последовательностями//В сб. "IX Международная конференция по проблемам теоретической кибернетики".- Ульяновск.- 1996.- с.16-17.

3. Батраева И.А. О свойствах образов автоматов при изменении порядка/ /В сб. "IX Международная конференция по проблемам теоретической кибернетики" Ульяновск.- 1996. - с. 17-18.

4. Батраева И.А. Замечание о строении геометрического образа конечного детерминированного автомата//В сб. "IX Международная конференция по проблемам теоретической кибернетики" -Ульяновск,- 1996. с.18-19.

5. Батраева И.А. О некоторых свойствах словарных отображений, непредставимых конечными детерминированными автоматами // Математика, механика, математическая кибернетика : Сб.науч.тр. Саратов:изд-во СГУ. 2000.- с.109-112.

6. Батраева И.А. Управляющие автоматы и анализ их свойств// Аналитическая теория автоматического управления и ее приложения. Труды Международной научной конференции.- Саратов. 5-9 июня 2000г. - с.224-229.

7. Батраева И.А. О некоторых свойствах геометрических образов автоматов// Радиоэлектроника и информатика. 2001. - №2. - с. 87-89.

8. Батраева И.А. О перечислении классов линейных последовательностных машин// Теоретические проблемы информатики и ее приложений. вып. 4. Саратов. Изд-во СГУ. - 2001. - с.20-25.

9. Богомолов A.M., Грунский И.С. О достижимости верхней границы длины минимального установочного эксперимента для автомата Мура // Кибернетика. 1971. - N1. - с. 147-148.

10. Богомолов A.M., Скобелев В.Г. Об одном алгоритме решения диагностической и установочной задач с автоматом // Кибернетика. 1975. - N 6. - с. 1-6.

11. Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем.

12. Киев.: "Наукова думка". 1974.

13. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987. - 392 с.

14. Габасов Р., Кириллова Ф.М., Крахотко В.В., Минюк С.А. Теория управляемости линейных дискретных систем // Дифференциальные уравнения. 1972. - т.8. - N5,6,7. - с. 767-774, 1081-1092, 1283-1292.

15. Гантмахер Ф.Р. Теория матриц. М.:Наука, 1988. - 552 с.

16. Гараев М.И., Фараджев Р.Г. Аналитические методы вычисления процессов в линейных последовательностных машинах с переменными параметрами // Автоматика и телемеханика. 1971. - N 1.- с. 66-74.

17. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1996. - 272 с.

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

19. Гинзбург С. О длине кратчайшего однородного эксперимента // Кибернетич. сб. вып. 3. - 1961.

20. Гинзбург С. Математическая теория контекстно-свободных языков.М.:Мир, 1970.

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

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

23. Клячко А.А., Рысцов И.К., Спивак М.А. Об одной экстремальной комбинаторной задаче, связанной с оценкой длины возвратного слова в автомате // Кибернетика. 1987. - N2. - с. 16-21,25.

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

25. Курош А.Г. Курс высшей алгебры. М.: Наука. - 1976. - 432.

26. Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г. Применение теории линейных последовательностных машин в системах диагностирования // Автоматика и телемеханика. 1988.- N8. с. 3-27.

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

28. Новиков П.С. Элементы математической логики. М.- Наука, 1973. - 400с.

29. Огнева М.В. Диссертация на соискание ученой степени к.ф.-м.н. "Эксперименты с линейными автоматами" 1999.

30. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. М. : Энергоиздат, 1981. - 319 с.

31. А.Ф.Резчиков, В.А.Твердохлебов. Управление и диагностирование в сложных системах. Саратов, изд. СГУ. - 1997. - 100 с.

32. Рысцов И.К. О слабой эквивалентности автоматов // Кибернетика. 1990. - N5. - с.85-89, 134.

33. Скобелев В.Г. О сложности поиска диагностических и установочных слов для конечного автомата // Кибернетика. 1985. - N4. -с.116-118.

34. А.К. Смирнов, В.А.Твердохлебов. Управление жизненными циклами сложных систем. Саратов, изд. СГУ. - 2000. - 110 с.

35. Спивак М.А. Некоторые свойства множества экспериментов автомата // Кибернетика. -1996. N6. - с. 1-7.

36. Твердохлебов В.А. Логические эксперименты с автоматами. Изд. Саратовского ун-та. - 1988. - 184 с.

37. Твердохлебов В.А. Универсальные генераторы тестов и системы диагностирования.//В сб.: Вопросы технической диагностики. Ростов н/Д: Рост.инж.-строит, ин-т. 1982. - с.106-110.

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

39. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы (поведение и синтез) М.:Наука, 1970. - 400 с.

40. Фараджев Р.Г. Линейные последовательностные машины. М.:Сов. радио. 1975.

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