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

• Тихончев, Михаил Юрьевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Тихончев, Михаил Юрьевич

Введение

Глава 1. Свойства контрольных экспериментов для детерминированных графов

1.1 Основные определения и обозначения

1.2 Безреверсный базис и его свойства

1.3 Существование и некоторые общие свойства контрольных экспериментов для детерминированных графов

Глава 2. Контроль детерминированных деревьев

2.1 Контрольный эксперимент для детерминированных деревьев

2.2 Контроль изоморфной вложимости

Глава 3. Контроль маркированных графов

3.1 Структура класса маркированных графов

3.2 Контрольные эксперименты для маркированных графов

Глава 4. Реализация контрольного эксперимента конечным автоматом

4.1 Автоматы, реализующие контрольный эксперимент

4.2 Автоматы с красками

4.2.1 Автомат с одной краской

4.2.2 Автомат с £(G) красками

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

Бурное развитие кибернетики и информатики стимулирует интенсивное развитие теории управляющих и вычислительных процессов, а также моделей (систем), реализующих эти процессы. Одной из основных моделей при этом является модель взаимодействия управляющей и управляемой систем (управляющего автомата и операционной среды) [1,2]. Взаимодействие этих систем зачастую представляется как процесс перемещения управляющего автомата по графу ("лабиринту") управляемой системы [2], что привело к возникновению обширной и интенсивно развивающейся области исследований поведения автоматов в лабиринтах [3-11]. Одним из направлений этих исследований является анализ с помощью автомата изображений, формальных языков, рабочих пространств робота и других дискретных систем.

Одна из центральных и актуальных проблем такого анализа известна как "проблема проверки правильности карты" [7,8]. Эта проблема состоит в следующем: задан конечный граф-эталон (карта) и определен класс исследуемых графов рабочих пространств. Требуется построить автомат, который, передвигаясь по произвольному графу из этого класса и воспринимая некоторую локальную информацию о вершинах пройденных путей, проверяет, изоморфен исследуемый граф эталону или нет. Процесс прохождения путей по графу, восприятия локальной информации о вершинах путей и вывода заключений о свойствах графа называется контрольным экспериментом над графом. При этом вершины и ребра исследуемого графа могут нести отметки, которые автомат во время эксперимента может изменять.

При исследовании проблемы проверки правильности карты наметилось несколько подходов. Один из них основан на том, что исследуемые графы являются конечными инициальными автоматами без выхода [3-5,12,13], т.е. конечными ориентированными графами с постоянными отметками на дугах. В рамках этого подхода найдены точные верхние оценки наименьшего времени, за которое различаются два графа, предложен метод построения контрольных экспериментов относительно класса всех таких графов, число вершин которых не превосходит числа вершин эталона. Второй подход заключается в рассмотрении лабиринтов, являющихся неориентированными конечными графами, и в процессе эксперимента на ребрах графа управляющий автомат расставляет отметки [6-11]. Предложен ряд методов проведения контрольных экспериментов относительно конечных классов исследуемых графов. Третий подход исходит из предположения, что лабиринты являются неориентированными графами с отмеченными вершинами [14-18]. Предложены методы различения таких графов и методы проведения контрольных экспериментов для конечных классов графов.

Результаты, полученные в рамках этих подходов, не образуют цельной картины и, в отличие от "классической" теории экспериментов с автоматами, заложенной Э.Муром и С.В.Яблонским и созданной трудами многих исследователей [2,19-22], исследования в этой области находятся в зачаточном состоянии. Поэтому разработка этой тематики чрезвычайно актуальна.

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

Описание управляемых систем такими графами используется в системах распознавания зрительных образов [23,24], в системах навигации роботов [6-11,23,24], в моделях представления знаний в интеллектуальных системах принятия решений [25], в системах поиска в сетях ЭВМ и в мультиагентных системах [26], при разработке операционных сред вычислительных систем [1]. Поэтому тематика диссертации актуальна как в теоретическом, так и в прикладном плане.

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

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

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

Введен новый класс /Г(М) всех детерминированных графов над алфавитом отметок М, у которых отметки любой пары различных вершин, смежных с одной и той же вершиной, различны. При этом отметки являются элементами заданного алфавита М. Класс /Г(М) включает класс детерминированных графов из [16-18] и содержится в классе детерминированных графов из [14-15]. Предполагается, что все рассматриваемые в работе графы принадлежат классу /Г(М). Получены следующие результаты:

1. Найден общий критерий существования контрольного эксперимента для произвольного графа-эталона относительно произвольного класса исследуемых графов. Из этого критерия следует, что если класс исследуемых графов совпадает с Я"(М), то контрольный эксперимент существует точно тогда, когда эталон является деревом. Полностью решена задача характеризации таких экспериментов. Для эталона-дерева предложен метод построения контрольного эксперимента относительно /Г(М) квадратичной (от числа вершин эталона) сложности. Предложен метод анализа результатов эксперимента для этого случая, позволяющий проверить не только изоморфизм эталона и исследуемого графа, но и наличие их изоморфного вложения друг в друга.

2. В классе ЛГ(М) выделен, возможно, бесконечный класс Ar(M,U), UcM, всех графов, у которых любой отметкой ueU, называемой маркером, отмечена не более чем одна вершина, и его подкласс /fm(M,U) всех графов, содержащих, по крайней мере, одну вершину, отмеченную маркером. Найдены критерии бесконечности, конечности и пустоты выделенных классов, их интересных подклассов и дополнения /Г(М, U) до /Г(М). Для случая, когда граф-эталон принадлежит классу /Tm(M,U), а класс исследуемых графов совпадает с ЛГ(М,и) предложено несколько способов построения контрольных экспериментов, различающихся априорной информацией о графе-эталоне. В случае, когда эталон задан полностью, эти способы позволяют построить

Ч Л контрольный эксперимент длины О(п), кратности 0(п ) и объема 0(п ), где п - число вершин эталона.

3. Предложен метод синтеза, который по любому контрольному эксперименту Р объема S(P) для некоторых эталона и класса исследуемых графов строит конечный автомат с ЗЭ(Р)-|Р|+2 состояниями, реализующий этот эксперимент за время 2Э(Р).

4. Предложен метод проведения контрольного эксперимента для произвольного детерминированного эталона G относительно класса УГ(М) конечным автоматом, который блуждает по исследуемому графу, исследует исходные отметки вершин и может ставить дополнительные отметки вершин нестираемыми красками. Предложен метод построения автоматов с одной или £(G) красками, где £(G) не превосходит числа п вершин эталона. При этом число состояний автомата, а также временная сложность проведения Л эксперимента не превосходят 0(п ) для автомата с одной краской и О(п) для автомата с k(G) красками.

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

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

Основные положения и результаты диссертации докладывались на конференции "Алгебраические методы дискретной математики" (Украина, Луганск, 2002), 5-ом международном конгрессе по математическому моделированию (Россия, Дубна, 2002), 8-ом международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2004), 6-ом международном конгрессе по математическому моделированию (Россия, Нижний Новгород, 2004), 6-ой международной конференции "Дискретные модели в теории управляющих систем" (Москва, МГУ, 2004).

Основные результаты диссертации опубликованы в работах [27-34], из которых [27,28,33,34] в соавторстве, остальные самостоятельно. В работах [27,28] диссертантом конструктивно введено понятие лабиринтной характеристики простого связного графа, доказано, что совпадение лабиринтных характеристик любой пары графов влечет их изоморфизм. Кроме того, для произвольного заданного графа-эталона предложен алгоритм синтеза конечного автомата с красками, который, взаимодействуя с произвольным простым связным графом, проверяет, изоморфен этот граф эталону или нет. В работе [33] диссертантом получен критерий существования контрольного эксперимента для произвольных детерминированного графа-эталона и класса исследуемых детерминированных графов, установлен ряд общих свойств таких экспериментов, найдена конструктивная характеризация контрольных экспериментов для эталона-дерева и обоснован способ построения такого эксперимента. В работе [34] диссертантом определен класс маркированных детерминированных графов, доказано существование и предложен способ построения контрольного эксперимента для маркированного эталона относительно класса всех маркированных графов.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Тихончев, Михаил Юрьевич

Заключение

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

Рассмотрен класс Л(М) так называемых детерминированных графов, у которых отметки любой пары различных вершин, смежных одной и той же вершине, различны. При этом отметки вершин берутся из алфавита М. Предполагается, что граф-эталон и исследуемые графы принадлежат классу /Г(М). Получены следующие результаты:

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

2. Показано, что в случае, когда класс исследуемых графов совпадает с ЛТ(М), контрольный эксперимент существует точно тогда, когда граф-эталон является деревом.

3. Найдена конструктивная характеризация контрольных экспериментов для эталона, являющегося деревом, относительно класса /Г(М).

4. Предложен метод построения контрольного эксперимента квадратичной (от числа вершин эталона) сложности для эталона-дерева относительно класса /Г(М).

5. Для произвольного контрольного эксперимента для эталона-дерева относительно класса Я(М) предложен метод анализа результатов проведения экспериментов, позволяющий проверить не только изоморфизм исследуемого графа и эталона, но и наличие изоморфного вложения друг в друга.

6. Определен, возможно, бесконечный класс A'(M,U), где Uc:M, всех графов из Л'(М) таких, что любой отметкой ueU, называемой маркером, отмечена не более чем одна вершина графа, и его подкласс /fm(M,U), состоящий из всех графов, содержащих, по крайней мере, одну вершину, отмеченную маркером. Найдены конструктивные критерии бесконечности, конечности и пустоты класса /f(M,U), его интересных подклассов и его дополнения до класса /Г(М).

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

2 3 кратности 0(п ) и объема 0(п ), где п - число вершин эталона.

8. Предложен метод синтеза, который по любому контрольному эксперименту Р объема Э(Р) для некоторого эталона относительно некоторого класса исследуемых графов строит конечный автомат с ЗЭ(Р)-|Р|+2 состояниями, реализующий этот эксперимент за время 2Э(Р).

9. Предложен метод проведения контрольного эксперимента для произвольного эталона G относительно класса /Г(М) конечным автоматом, который блуждает по исследуемому графу, исследует исходные отметки его вершин и может ставить дополнительные отметки вершин нестираемыми красками. Предложен метод построения автоматов с одной или £(G) красками, где £(G) не превосходит числа вершин эталона. При этом число состояний автомата, а также временная сложность проведения эксперимента не превосходит 0(п ) для автомата с одной краской и О(п) для автомата с £(G) красками.

Эти результаты являются новыми и завершенными.

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

Список литературы диссертационного исследования кандидат физико-математических наук Тихончев, Михаил Юрьевич, 2005 год

1. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. -М.: Наука, 1988, 296 с.

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

3. Кудрявцев В.Б., Уитумлич Щ., Килибарда Г. О поведении автоматов в лабиринтах // Дискретная математика, 1992, Т. 4, вып. 3, С. 3-28

4. Килибарда Г., Кудрявцев В.Б., Уитумлич Щ. Независимые системы автоматов в лабиринтах // Дискретная математика, 2003, Т. 15, вып. 2, С. 3-39.

5. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Коллективы автоматов в лабиринтах // Дискретная математика, 2003, Т. 15, вып. 3, С. 3 40.

6. Levitt Т., Lawton D.T. Qualitative navigation for mobile robot // Artificial Intelligence, 1990, -v.40. P. 306-360.

7. Dudek G., Jenkin M, Milios E., Wilkes D. Map validation and Robot Self-Location in a Graph-Like World // Robotics and Autonomous Systems, 1997, -v.22(2). — P. 159-178.

8. Dudek G., Jenkin M, Milios E., Wilkes D. Map validation in a graph-like world. In 13th International Joint Conference on Artificial Intelligence, 1993 -P. 1648-1653.

9. Dudek G., Jenkin M, Milios E., Wilkes D. Robotic exploration as graph construction // IEEE Trans. On Robotics and Automation, 7(6), 1991, -P. 859-864.

10. Kuipers В., Levitt T. Navigation and mapping in large-scale space // AI Magazine, 1988, Vol. 9, n. 2 P. 25-43.

11. Kuipers B. The Spatial Semantic Hierarchy // Artificial Intelligence, 2000, -Vol. 119, n. 1-2,-P. 191-233.

12. Кудрявцев ПО. Об отличимости вершин автоматных лабиринтов конечными автоматами // Дискретная математика, 1991, Т. 4, вып. 4, С.143-152

13. Груиский И.С., ОлеГшик Р. И. Об отличимости инициальных лабиринтов конечными автоматами // Интеллектуальные системы, 1999, Т. 4, вып. 1-2, С. 273-283

14. Груиский И.С., Курганский А.Н. Языки графов с помеченными вершинам // Труды ИПММ НЛНУ, 2004, -Т. 9, С. 53-60.

15. Сапунов С.В. Эквивалентность помеченных графов // Труды ИПММ НАНУ, 2002, -Т. 8, С. 162-167.

16. Груиский И.С., Сапунов С.В. Контроль графов с отмеченными вершинами // Труды ДГТУ, сер.: Выч.техника и автоматика, вып. 38, 2002, С. 226-232.

17. Сапунов С.В. Контроль детерминированных графов // Труды ИПММ

18. НАНУ, 2003, Т. 8, - С. 106-110.th

19. Tan Q.M., Petrenko A. Testing of communication systems, IFIP 1Г Int.1. Workshop, 1998,-P. 83-99.

20. Яблонский С.В. Некоторые вопросы надежности и контроля управляющих систем // Сб. "Матем. вопросы кибернетики", 1988, вып. 1, С. 5-25

21. Сперанский Д.В. Эксперименты с линейными и билинейными конечными автоматами: Учеб. пособие, Саратов: Издательство Саратовского университета, 2004, - 144 с.

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

23. Люггер Дж.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем. М: Издательский дом "Вильяме", 2003, - 864 с.

24. Negnevitsky М. Artificial Intelligence. A guide to intelligent systems. -Addison-Wesley, 2002, 394 p.

25. Вагин B.H. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988,-384 с.

26. Девятков В.В. Системы искусственного интеллекта: Учебное пособие для вузов. М.: Издательство МГТУ им. Н.Э.Баумана, 2001, - 352 с.

27. Груиский И.С., Тихоичев М.Ю. О распознавании графов конечным автоматом. Вестник Донецкого университета. Серия А. Естественные науки 2001. - №2. - С. 351-356.

28. Груиский И.С., Тихоичев М.Ю. Идентификация топологических свойств среды взаимодействующим с ней автоматом. Сборник тезисов конференции "Алгебраические методы дискретной математики" Луганск, Украина, 23-27 сентября 2002 г., С. 69-70.

29. Tikhonchev M.Yu. The Recognition of the Environment by Finite Automaton. Book of Abstracts of 5th International Congress on Mathematical Modeling, Dubna, Moscow region, Russia, September 30 October 6, 2002, Vol. 2, p. 134.

30. Tikhonchev M.Yu. Checking Experiment for Determinate Trees. Book of Abstracts of 6th International Congress on Mathematical Modeling, Nizhny Novgorod, Russia, September 20 26, 2004, p. 377.

31. Тихоичев М.Ю. Распознавание детерминированных графов конечным автоматом. Труды VI международной конференции "Дискретные модели в теории управляющих систем", Москва, 7-11 декабря, 2004, Москва: Изд.отдел ф-та ВМиК МГУ, С. 214-219.

32. Грунская В.И., Тжопчев М.Ю. Контроль детерминированных графов с маркерами // Теоретические проблемы информатики и ее приложений: Сб. научных трудов под ред. проф. А.А.Сытника. -Изд-во Саратовского университета, 2004, С. 223-232.

33. Гросс М., Лантеп А. Теория формальных грамматик. -М: Мир, 1971. -294 с.

34. Харари Ф. Теория графов. -М.: Мир, 1973, 300 с.

35. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. - 280 с.

36. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003, -1104 с.

37. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы // Труды МИАН им. В.А.Стеклова, 2000, т. 231, С. 134-214.

38. Максима 1ко И.К Эксперименты в финитно-определенных метрических пространствах автоматов: Дисс. канд. физ.-мат. наук; 01.01.09 / СГУ. -Саратов, 1999,-128 с.

39. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа, М.: Наука, 1972, - 496 с.

40. Математическая энциклопедия / Гл. ред. И.М.Виноградов. М.: Советская Энциклопедия, т. 4. 1984. 1216 стб.

41. Грунский И.С., Максименко И.И. Эксперименты с маркированными автоматами. Препринт № 96.02 ИПММ НАНУ, ноябрь 1998, 33 с.

42. Гжл А. Введение в теорию конечных автоматов. М.: Наука, 1966, - 272с.45. /lxo Л.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы, -М.: Издательский дом "Вильяме", 2000, 384 с.

43. Насырое A3. Об обходе лабиринтов автоматами, оставляющими нестираемые метки. Дискретная математика. 1997, Т. 9, № 1, С. 123-133

44. Дэ/с. Маккопнелл. Анализ алгоритмов. Вводный курс. Москва: Техносфера, 2002, - 304 с.

45. Кук Д., Бет Г. Компьютерная математика. -М.: Наука, 1990, 384 с.