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

На правах рукописи

Тихончев Михаил Юрьевич

i

Автоматный анализ детерминированных графов

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

кибернетика

Автореферат

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

Саратов 2005

Мею 6

Па правах рукописи

Тихончев Михаил Юрьевич

Автоматный анализ детерминированных графов

Специальность 01.0] .09 - дискретная математика и математическая

кибернетика

Автореферат

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

Саратов 2005

Диссертационная работа выполнена на кафедре математики и информатики филиала Ульяновского государственно! о университета в г Димитровграде

Научный руководитель: доктор технических наук, профессор

Сперанский Дмитрий Васильевич

Официальные оппоненты: доктор физико-математических наук, профессор

Мельников Ьорис Феликсович

кандидат физико-математических наук, профессор Салий Вячеслав I Ьиколаевич

Ведущая организация: Московский пхударственнъш университет им.

М.В Ломоносова, г. Москва

Защита состоится г в Л' часов на заседании диссертационного

совета К 212 243.02 по присуждению ученой степени кандидата физико-математических наук при Саратовском государственном университете им Н. Г Чернышевского по адресу 410012, г Саратов, ул Асфаханская. д. 83, СГУ, механико-математический факулыет

С диссертацией можно ознакомиться в библиотеке Саратовского государшненного университета им. Н. Г Чернышевского

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

Ученый секретарь диссертационного совета, кандидат физ.-мат наук,

доцент С КорневВ В

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

I ияМ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

При исследовании проблемы проверки правильности карты наметилось несколько подходов. Один из них основан на том, что исследуемые графы являются конечными инициальными автоматами без выхода, т е конечными ориентированными графами с постоянными отметками на дугах В рамках этого подхода в работах В.Б.Кудрявцева, Г Ю Кудрявцева, И С Грунского и Р.И.Олейника найдены точные верхние оценки наименьшего времени. ?а которое различаю!ся два графа, предложен метод построения контрольных экспериментов относительно класса всех таких графов число вершин которых не превосходит числа вершин эталона. Второй подход заключается в рассмотрении лабиринтов, являющихся неориентированными конечными графами, и в процессе эксперимента на ребрах графа управляющий ашома! расствляет отмсти. В работах Т.Левипа и 1 Дудека предложен ряд методов проведения контрольных экспериментов относшелыю конечных классов исстедуемых графов Третий подход исходит из предположения, что лабиринты являются нсориешированными графами с отмеченными вершинами В работах

С В Сапунова пред ю/ксны меюды различения таких графов и метопы проведения кош рольных экспериментов для конечных классов графов

Резульгаш, подученные в рамках тгих подходов, не образуют цельной картины и, в огличис 01 ' классической" теории экспериментов с автоматами, заложенной ') Муром и С В Яблонским и созданной трудами Л.М Богомолова, В Б.Кудрявнева. С В Алешина, Л С Подколзина, Д В.Сперанского и И С.Грунского, исследования в этой области находятся в зачаточном состоянии Поэтому разрабо1ка этой темашки чрезвычайно актуальна

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

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

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

Новые научные резулм :ны и положения, выносимые на защиту.

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

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

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

2 В классе ЛТМ) выделен, возможно, бесконечный класс К(Ш,II), 1!сМ, всех трафов, у которых любой отметкой иь!1, называемой маркером, отмечена не более чем одна вершина, и его подкласс АГт(М,и) всех 1рафов, содержащих, по крайней мере, одну вершину, отмеченную маркером. Найдены критерии бесконечности, конечности и пустоты выделенных классов, их интересных подклассов и дополнения ЛТ(М, II) до ЛТ(М). Для случая, когда граф-эталон принадлежит классу Я,„(М,и), а класс исследуемых графов совпадает с А"(М,и) предложено несколько способов построения контрольных экспериментов, различающихся априорной информацией о графе-эталоне. В случае, когда э1алон задан полностью, эти способы позволяю! построив контрольный эксперимент длины О(п), крашосш 0(п2) и объема 0(п3), где п - число вершин Э1алона.

3. Предложен метод синтеза, который по любому контрольному эксперименту Р объема $(Р) для некоторых эталона и класса исследуемых графов строит конечный авюмат с 3&(Р) |Р| 12 состояниями, реализующий этот эксперимент за время 2Э(Р) 4 Предложен метод проведения контрольного эксперимента для произвольною детерминированного эталона О относительно класса АГ(М) конечным автомаюм, который блуждает по исследуемому 1рафу, исследует исходные о I метки вершин и може! С1авигь дополнительные отметки вершин нестираемыми красками Предложен метод построения автоматов с одной или НО) красками, где к(С>) не превосходит числа п вершин л ¿л она. При этом число состояний автомата, а также временная сложность проведения эксперимента не превосходят ОСп3) для автомага с одной краской и О(п) для автомата с НО) красками Эти результаты являются новыми и завершенными Таким образом, впервые получен ряд критериев существования, методов построения и автоматной реализации контрольных экспериментов для ле1ерминированных графов относительно потенциально бесконечных классов исследуемых графов.

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

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

Публикации. Но результатам диссертации опубликованы 8 работ, из которых [1,2,7,8] в соавторстве, остальные самостоятельно. В работах [1.21 диссертантом конструктивно введено понятие лабиринтной характеристики простого свяпюто графа, доказано что совпадение лабиринтных характеристик любой пары графов влечет их изоморфизм. Кроме ют о, для произвольною заданного графа-эталона предложен алгоритм синтеза конечного автомата с красками, который, взаимодействуя с произвольным простым связным графом, проверяет, изоморфен этот граф эталону или нет В работе [7] диссертантом получен критерий существования контрольного эксперимента д тя произвольных детерминированного графа-эталона и класса исследуемых детерминированных графов, установлен ряд общих свойств таких экспериментов, найдена конструктивная характеризация контрольных экспериментов для эталона-дерева и обоснован способ построения такого эксперимента В работе [8] диссертантом определен класс маркированных детерминированных графов, доказано существование и предложен способ построения контрольною эксперимента для маркированного эталона относительно класса всех маркированных графов

Объем и структура диссертации. Диссертация содержит ИЗ машинописных страниц и состоит из введения, четырех глав, заключения и списка литературы, включающего 48 наименований

СОДЕРЖАНИЕ РАБОТЫ

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

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

В разделе 1.1 введены основные понятия и обозначения. Вводится класс АТ(М) всех конечных, простых (т е без петель и кратных рёбер), связных, помеченных, инициальных, неориентированных фафов 0=(8г„Ео,Хо,ц,йо)- где 8г, - конечное множество вершин, Е0 - множество рёбер, ХссМ подмножество фиксированного конечного непустого алфавит отметок М, р: >Х(:, - сюръективная функция разметки вершин такая, что отметки всех вершил, смежных одной вершине, попарно различны, ^ - инициальная вершина. ДМ) - класс всех деревьев из /Т(М) М+ -множество всех непустых слов в алфавше М, е - пустое слово, М*=М+и{е}, М)-Ми{е}

Для всякого множества ОсМ+ через К(0) будем обозначать его замыкание по всем непустым начальным отрезкам входящих в него слов Для любою слова ю=Х) ..хк, х,еМ, 1< 1 <к, через сг>~' будем обозначать слово хк...х]. Если Р—{со,} некоторое множество слов, то через Р"' обозначим множество {о,"'}.

Определим на М' частичную операцию склеивания о. Пусть х,уеМ, а>,0£М*, тогда юхохо_(йхо и юхоуо не определено, если кт-у.

Конечную последовательность вершин р=§г...£к такую, что при к>1 <&,&ц>сЕ(„ 11 1 <к. назовем путём длины (к-1) в графе О Последовательность р/р)-^)). .р^) назовем О1меткой пуш р. Отметку любого пути, исходящего из вершины gcSr„ будем называть словом, порожденным вершиной g. Язык /,£ определим как множество всех нов, порожденных вершиной Вершины g,heSG назовём неотличимыми, если

Lg-Lh, и отличимыми в противном случае Граф в называется приведенным если все и о вершины попарно отличимы Множество Lg0, где go инициальная вершина графа О, назовём языком, представимым 1рафом О, и обозначим сю Ь(, Через ¿с,к будем обозначать множество всех слов языка ¿г, длиной не более к.

Язык назовем древесным, если О - дерево Будем также говорить, чю язык представим графом, и писать ЬеСгарИ, если существует такой граф Ое/Г(М), что и,=Ь.

Через £*(о, йбМ+, обозначим вершину графа О, в коюрой заканчивается

и}гь с о1меткой со, исходящий из вершины если такой путь существуе! и будем считан,, что g*я) не определена в противном случае

Ьу,лем говорить, что графы О и Н из класса АГ(М) изоморфны, и обозначать гго Ст~Н, если между множествами их вершин существует биекция, сохраням>шая смежность, отмежи вершин и инициальную вершину Считаем, что класс АГ(М) определен с точностью до изоморфизма

Конечное множество слов Р<г~М+ назовём контрольным эксперименюм для графа С' ЛШ) относитетьно класса М), если для любого графа Нр/^из ¿цпР = ¿(,пР следует С = II Граф О при этом будем называть графом-эталоном (или просто эталоном), а ^ - классом исследуемых трафов, и. если не оговорено противное, под эталоном будем понимать только графы с числом вершин больше или равным двум

Мощное 1Ь |Р1 контрольного эксперимента Р назовем его кратностью, длину /(Р) ею наибольшего слова - длиной эксперимента, сумму 9(Р) длин всех слов из Р -объемом эксперимеша

В разделе 1 2 вводятся понятия безреверсного базиса слова и безреверсного базиса языка в алфавите отметок М Слово к>=Х] хь х,еМ, 1<Ик, назовем безреверсным, если либо к<3, либо при к>3 для любого 1 2<Щк 1), х.^/х,^

Безреверсным базисом произвольного слова (оеМ+ назовем множество Б[<в]сМ+, которое зададим конструктивно, следующим образом.

1 Положим Б[со]={со},

2 Если какое-либо слово и из Б[со] не является безреверсным, те. имеет вид и=ахух|3, а,|}с М*, х,уе М, то добавим в Б[со] слова аху и ахр и удалим из Б[о>] слово о;

3 Когда в множестве Б[га] останутся только безреверсные слова, удалим из Б[т] все слова, являющиеся начальными отрезками какою-либо другого слова из Б[со].

Безреверсным базисом любого ячыка 1сМ\ назовем множество Б|Х] =- Щ®]

(йе/.

Пусть 8с-{§0, ,}, где go - инициальная вершина графа О Множество

кратчайших бсзреверсных слов У(О)={и0,. .о^, ,} ;аких. что и„ ГККЗЯг,| 1, есть отметка пути, исходящего из и заканчивающеюся в назовём базисом достижимости графа О

Основными результатами раздела 1 2 являются следующие утверждения Следствие 1.2.2. Для любых графов О и Н из класса АГ(М) ¿с-Ц] тогда и тотько тогда, кот да Б[Хс]=Б[1н]

Лемма 1.2.3. Язык ЬеОгарИ является древесным тогда и только Ю1да, когда его безреверсный базис конечен

Лемма 1.2.4. Безреверсный базис древесного языка совпадает с базисом достижимости представляющего его дерева.

Лемма 1.2.5. Любые тва дерева из класса 7'(М) июморфны тогда и только юг да, когда их базисы достижимоеiи совпадают

Согласно следствию 1 2 2, язык, предегавимый дс!ерминированным графом, однозначно определяется его безреверсным базисом. Леммы 12 3-1.25 устанавливают важные свойства детерминированных деревьев, представимых ими языков и их базисов достижимости Любое дерево из класса Г(М) определяется с точностью до изоморфизма своим базисом достижимости, который в свою очередь совпадает с безреверсным базисом представляемо! о этим деревом языка

В разделе 1 3 рассматривается проблема существования контрольно! о эксперимента для заданного графа-эталона относительно различных классов исследуемых графов, и исследуются его общие свойства Прежде веет о, вводится следующая псевдометрика на графах из класса iT(M) Расстоянием между двумя любыми графами G HcJTflVf), A(j/£n, назовем величину p(G,H)-l/k такую, что L(,VZ,ak и Lq '=ЛнЫ Если то положим p(G,H)=0. Граф Gs=iT(M) называется

предельным графом класса ftJir(M) и обозначается Gclim F, если для любого е^О найдется граф HeF-{G} такой, что p(G,H)^s В 1тротивном случае будем писать G?"lim F Будем юворить, что графы G и II из класса ЛТ(М) k-неотличимы, и писать (G,H)e% если Через ¿t(G) обозначим класс всех трафов из ЩМ) к-

неотличимых ох G.

Теорема 1.3.1. Пусть F- произвольный непустой подкласс класса JP(M). Тогда следующие утверждения равносильны:

1) Существует контрольный эксперимент для трафа СеЙГ(М) относительно класса F,

2) ¿ii(G)r\/rc{G} для некоторого к;

3) Gglirrt F.

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

Доказано, что контрольный эксперимент относительно класса /¡Г(М) всех детерминированных 1рафов существует тогда и только тогда, когда граф-эталон * является деревом.

Далее в разделе 1.3 исследован ряд общих свойств контрольных экспериментов для детерминированных графов, при выводе которых не конкретизируются ни вид графа-эталона, ни класс исследуемых трафов Предполагается лишь существование контрольного эксперимента для некоторого эталона из класса К(Ш) относительно некоторот о Henycioi о подкласса F класса А(М) Установлено, что безреверсный базис контрольного эксперимента для графа ОеАГ(М) относительно класса Fc_K(М), тоже является контрольным экспериментом для G относительно класса F Также

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

Во второй главе рассмафивакнся задачи построения контрольного эксперимента для дегер минированных деревьев относшсльно класса ДМ) и проверки с использованием контрольного эксперимента изоморфной вложимосга как исследуемого графа в эталон-дерево, так и эталона в исследуемый граф.

Раздел 2 1 посвящен задаче построения контрольного эксперимента для произвольного эталона Т е= 7Т[М) относшсльно класса АГ(М).

Для всякого графа ОеЛГ(М[) его свободным базисом достижимости УР(О) тшовем конечное множешво слов из 1С, такое, что для любой вершины g,<FSG, 0<К|8о|-1, в \Т(0) найдется, по крайней мере, одно такое слово со,, что Через УГ(С)

обозначим класс всех свободных базисов досшжимости графа О.

Для произвольного дерева ТеГ(М) и слова <оеМ+ определим слово Уг(оэ) следующим образом:

- если слово со имеет вид со^хсог, где сй|,со2еМ*, хеМ, причем сои соеДь где J - дерево, полученное добавлением к 1 вершины Г, р.(т )- х, и ребра ■Оо*(йь1 >, то положим/т(«>)=Ю1Х ;

- иначе, положим/¡-(ю)=е.

Для множества слов Ос М+ и дерева Те ДМ), определим /т(0) как множество

слов./т(0)--

ше(3

Центральным результатом раздела 2.1 является следующая теорема Теорема 2.1.3. Конечное множество слов РсМ+ является конгрольным экспериментом для эталона Тг Г(М) относительно класса АТМ) тогда и только тогда когда Я(Рп1т)'=^(Т) и в ИЛТ) найдется такой свободный баше досшжимосги VI П), что/Т(Р />т) содержит (\Т(Т)М) 1Х.

'Георема 2 1 3 формулирует конструкшвиый критерий позволяющий для любого конечного множества слов проверять- является это множество контрольным экспериментом для эталона-дерева Т<-7ТМ) относи1ельно класса /Г(М) или нет Следующая теорема предлагает один из способов построения такого эксперимента 'Георема 2.1.4. Множество слов С,(Т)^Б[У(Т)М!] является контрольным экспериментом для эталона Те 7ТМ) относительно класса К(М)

Кратность эксперимента С|(Т) составляет п(1М! 1)-2, а длина не превосходит пА1, где п - число вершин дерева Т Объем этого эксперимента сос1авляет не менее 2!М1+3(!М|-1)0т-1)-Ч, и не превосходит 2|МИ|М'-1)(п-1)(п + 4)/2+1 Исли считать временем проверки исследуемого графа на изоморфизм эталону Т число

перемещений автомата по вершинам исследуемою графа, то асимптотическая оценка временной сложности такой проверки с использованием контрольного жеперимента С,(Т) в наихудшем случае составляет 0(п2)

Утверждение 2.1.1. Если РсМ^ - контрольный жеиеримет для эталона IV ЯМ) относитетьно класса 7ТМ) то Р является гакже контрольным экспериментом для Т относительно класса ДМ)

Согласно утверждению 2 1 1 задачи построения контрольных экспериментов для дерева Тс 7ТМ) относительно классов 7ТМ) и ДМ) эквивалентны.

В разделе 2 2 рассматривается задача контроля с помощью контрольною эксперимента изоморфной вложимости для детерминированных деревьев Основные результаты этого раздела сформулированы в следующих теоремах Теорема 2.2.1. Ьсли Рс_.М' контрольный эксперимент для эталона ТеГ(М) относительно класса ДМ), то любой граф 11<=,ЛГ(М) шоморфно вложим в Т тогда и только югда, когда Б[11(Р)]п1„*0 и Б[К(Р)]п1нсБ[К(Р)]г1/_т.

Теорема 2.2.3. Пусть РсМ+ - ко1ггрольный эксперимент для эталона ТсГ(М) относительно класса К{Ш) и .) - произвольное дерево из класса Г(М). Тогда равносильны следующие утверждения:

1) Т изоморфно вложим в .1;

2) Б[Р]гЛтс/_).

Теорема 2.2 1 показывает, как с помощью контрольного эксперимента можно проверить, является исследуемый траф из класса 1Г(М) изоморфно вложимым в эталон-дерево или нет Согласно теореме 2 2.3, с использованием контрольною эксперимента можно проверять изоморфную вложимость лалона из Т(М) в исследуемый граф, если исследуемый граф тоже является деревом.

В третьей главе исследуется специальный, возможно, бесконечный класс ЩМДГ), где и с М. графов из К(М), в каждом из которых любой отметкой ие11 отмечена не более чем одна вершина причем множество и заранее задано Элементы множества и назовем маркерами, а любой граф из класса АГ(М,И), содержащих по крайней мерс, одну маркированную вершину, маркированным графом Через Л"т(МД1) обозначим подкласс всех маркированных графов из Х"(М,и) Положим ^(М.и)=ЖМ,иНГт(М.и), Т(М. и)=Ж(М)-ДМЛ1)

В разделе 3.1 исследуются свойства классов ДГ(М,и). ЛГт(М 1Г) ЛЧ(М,и) и АТМ, I/) Найдены конструктивные критерии пустоты, конечности и бесконечности этих классов в терминах свойств множества маркеров

Раздел 3 2 посвящен задаче построения контрольных жепериментов для маркированных 1рафов Установлено что ни для какою Сс.КШ)-7ТМ) не сущеавует контрольного эксперимента относительно класса А"(М, и) Рассмотрен подкласс /Га(М.и) класса УГ(М.и), состоящий из всех графов, имеющих, по крайней

мере, две охличимые вершины, отмеченные одинаковым маркером ис11 Для произвольного графа ОеАГа(М,и) установлена справедливость следующею утверждения.

Теорема 3.2.1. Для любого эталона в из класса А"а(М,и) сугцесшуа контрольный эксперимент относительно класса ЩМ)-ЛГа(М,и) крашости не более 3 и длины не более 2п-|Хо|, где п - число вершин графа О.

Следующая теорема устанавливает существование контрольного эксперимента для графа-эгалона из класса 11) и.йГга(М,и) относшельно класса /ГЬ(М,11) Теорема 3.2.2. Для любого эталона О из класса #(М,и)и.йГт(М,и) сущее хвует контрольный эксперимент относительно класса ЯГм(М,С) кратности один, длиной не более п для случая 0£А"ш(М,и) и не более (п-1) для случая вг Л(М. V), где п - число вершин графа в

Пусть исЬ' - произвольный фиксированный маркер Обозначим через АГ|(М.и) класс, состоящий из всех таких графов О, что в О найдется пара смежных вершин g' и

отмеченных символом и. Для 1рафов из класса 2Г|(М,и) справедлива следующая теорема о существовании контрольного эксперимента

Теорема 3.2.3. Для любого эталона О из класса ¿^(М,^ сущесшует контрольный эксперимент относительно класса ЛГ(М)-А'1(М,и) кратности один и длиной не более п, где п - число вершин графа в.

Разобьем класс ,йГт(М,и) на два непересекающихся подкласса Гт=А„,(М,и)г>7"(М) и 2т=Кт(М,иуТт.

Теорема 3.2.6. Для любого эталона О из класса Zra множссшо слов

где п - число вершин эталона, является контрольным экспериментом для в

относительно класса АГ(МД1).

Теорема 3 26 устанавливает существование конгрольного эксперимента для маркированных графов, не являющихся деревьями, относительно класса ЩМ,и) Нетрудно показать, что утверждение этой теоремы остается справедливым и в том случае, когда эталон О - дерево Д,ш любого 1рафа О из класса АГ(М) через и0сХ0 обозначим множество всех таких отметок х вершин графа О, для которых существует единственная вершина gcSG такая, что Следующая теорема обобщает

утверждение георемы 3 2.6.

Теорема 3.2.7. Для любого тако1 о эталона Б из класса ЩМ), что ис^0, множество слов С^(0)=£о2" 2МЬ где п - число вершин графа О, является контрольным

экспериментом относшельно класса АТМ,{х})

« ис

Контрольный эксперимент С3(0) дчя графа Ос£т опюситепьно класса имеет длину О(п) и кратность не менее 0(2"). Следовательно, объем указанною эксперимента оценивается как величина не менее 0(п2п) Таким образом, ука<анньш

контротьный эксперимент может эффективно использоваться только д 1я »талонов с очень небольшим числом вершин п.

Для произвольною графа ОгЛГт(М,1!) определим ДУСв)-^, .,и>„ ,}, как

множество кратчайших слов из М* таких, что для любой вершины §,е Ьо (КК^оН найдется такая маркированная вершина что g,=gmCl)*w,

Теорема 3.2.8. Для любою эталона ОсЛГт(М,и) множество слов )} является контрольным экспериментом для О относительно класса Л(М,и).

Длина предложенного в теореме 3 2 8 эксперимента С6(0) не превосходи! 2(гН 1)-|ипХо'. а кратность не превосходит п2('МН-1)+п(п |Х&|41) Асимптотическая оценка временной сложности проверки исследуемого графа на изоморфизм графу-эталону О с использованием контрольного эксперимента С6(0) состав 1яет не ботее 0(п3) Следовательно, указанный контрольный эксперимент в отличие от эксперимента С5ССт)=Л(-,2п"2М1 может эффективно использоваться для эталонов с большим числом вершин п

Пусть /т(М,и) - подкласс класса ЛГт(МД1), состоящий из всех графов с маркированной инициальной вершиной Тогда справедливо следующее Следствие 3.2.7. Для любого графа 0«=/т(М,и) множество слов Сй'(0)=У(С)М|о{'У(0)М1} ' является контрольным экспериментом для О относительно класса ЛГ(М,и).

Пусть О любой граф из класса А"т(М,и), go - его инициальная вершина, gra -любая маркированная вершина графа О Чере! ат обозначим отметку аут в в, исходящего из g0 и заканчивающегося в Через G(gm) обозначим граф, полученный из О назначением инициальной вершины gm вместо Следующая теорема предлагает еще один способ построения контрольного эксперимента для графа Ое/Гт(М,и) относительно класса ЛЩ, 11)

Теорема 3.2.9. Для любого графа О из класса /СшС\1,и) множество слов С7('0)=ашоУ(0^га))М1о{У(0(§т))М1}"1 является контрольным экспериментом для О относительно класса ЛТМ.Т1)

Кратность эксперимента С7(в) оценивается как 0(п2) а длина не превосходит Зп Асимптотическая оценка временной стожносш проверит исследуемого графа на изоморфизм графу-эталону О с использованием контрольного эксперимента С7(0) составляет не более 0(п3). т е имеег одинаковый порядок с временной сложностью такой проверки с использованием эксперимента Се/в) Однако д 1я эксперимента С ,ГО) не требуется построения множества \У(0)

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

исследуемых графов Этот автомат взаимодействует с исследуемым графом как с лабиринтом

Под конечным автоматом А будем понимать конечный, всюду определенный, инициальный автомат Мили с заключительными состояниями, те семёрку <А.В,8,ф,и,8е,5о>. где А и В - входной и выходной алфавиты, соответственно, Б -конечное множество состояний, со и у - функции переходов и выходов, соответственно, 8сс8 множество заключительных состояний, з0е$ - начальное состояние Перейдя в любое из заключительных состояний, автомат останавливается.

Для произвольною 1рафа-эталона О из класса АТМ) требуется построить конечный автомат А(О). который, взаимодействуя с произвольным графом Н из класса /сЛГСМ), через конечное число шагов определяет- Н изоморфен эталону или нет

В разделе 4.1 для любот о контрольного эксперимента Р для графа в относительно класса Р предложен метод синтеза автомата А(Р) (без красок) с числом состояний 39(Р)-|Р|4-2. проверяющий произвольный граф из класса Fна изоморфизм графу С не более чем за 29(Р) временных тактов Входной алфавит А автомата А(Р) определяется как Мх2м. а выходной алфавит В равным множеству Мо{Л} Вход и выход автомата А(Р) интерпретируются следующим образом. Находясь в т-ый тают времени в вершине Ь графа Н, автомат получает на вход пару (а1„а2,)еА, где а',_р(Ь) - отметка вершины И, а2, множество отметок всех вершин трафа Н, смежных с Ь Выходной символ Ь,еВ интерпретируется как команда автомату переместиться в вершину отмеченную символом Ь„ если или остаться в той же вершине при Ь,_Л

В раздете 4.2 для произвольного графа Ое/Г(М) разработаны алгоритмы синтеза автоматов с одной и ¿(в) красками, реализующих контрольный эксперимент для графа О относительно класса АГ(М) причем к(О) не превосходит п, где п - число вершин графа в.

Пусть Мр конечное множество дополнительных отметок, называемых красками Не ограничивая общности, будем считать, что Мр={1,2. ,Мр1} Будем также полагать, что в начальный момент всем вершинам исследуемых графов кроме основных отметок приписана дополнительная отметка 0 Через Ма(и обозначим множество всех дополнительных отметок Ма(И=Мг/ Jft()}

В пункте 4.2 1 описывается синтез конечного автомата с одной краской ^={1}) Потребуем, чтобы автомат начинал свое взаимодействие с трафом с раскрашивания ею инициальной вертпины, тес приписывания ей дополнительной отметки 1 При дальнейшем взаимодействии с трафом автомат больше не приписывает дополнительной отмегки никаким вершинам исследуемою графа ГТусть О - граф из класса ЩМх(0,1)), полученный из графа О приписыванием топотнительной отметки 1 его инициальной вершине и допо шитедьных отметок О

всем его остальным вершинам Гогда требуемый автомат /1(G) получается из автомага /1(C(/(G*)), где C6'(G*) - контрольный эксперимент из следствия 3 2 7, добавлением условия начинать взаимодействие с исследуемым графом приписыванием дополнительной отметки i ею инициальной вершине Число состояний и временная сложность реализации контрольного эксперимента для полученною автомата .4(G) с одной краской оцениваются как 0(п3), где п число вершин графа G

Пункт 4 2 2 посвящен задаче синтеза автомата с k(G) красками, где &(G) не превышает числа вершин трафа G Рассмотрение задачи начинается с построения специального алгоритма обхода графа методом поиска в глубину с нумерацией сто вершин Конечное множество MP(G)~{1, .,WG)}, где k(G) - максимальный номер, приписанный вершинам графа G при его обходе, будем называть множеством красок Предложенный алгоритм обхода порождает специальную лабиринтную характеристику X(G) трафа G в виде последовательности векторов отметок окрестностей вершин графа в порядке прохождения этих вершин. Показано, что временная сложность этого алгоритма составляет О(п)

Теорема 4.2.1. Любые графы G и П из класса JT(M) изоморфны toi да и только тогда, кот да их лабиринтные характеристики совпадают.

Согласно теореме 4 2 1 лабиринтная характеристика X(G) произвольного графа GeiT(M) является ею полным инвариантом

На основе лабиринтной характеристики X(G) эталона G предложен алторитм синтеза автомата /4(G) с k(Q) красками, который имеет 2п+1 состояние и реалитует контрольный эксперимент для графа G относительно класса jRT(M) не более чем за 2п-1 временных тактов

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

Основные результаты работы опубликованы в:

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

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

3 Tikhonchev М 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

4 Тихончее МЮ Контрольный эксперимент для детерминированных графов с уникальной отметкой. Материалы VIII международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004 г.) -М.. Изд-во механико-математического факультета МГУ, 2004, С. 314 - 316.

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

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

7 Грунская В И, Тихончее МЮ Контроль детерминированных деревьев // Ученые записки Ульяновскою i осу дарственного университета. Сер. Фундаментальные проблемы математики и механики. Вып 1(14) / Под ред. академ. РАЕН, проф А.С.Андрсева. - Ульяновск: УлГУ, 2004, С. 4-17

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

«

?

«

,16 0 8 0

РНБ Русский фонд

2006-4 11006

Введение

Глава 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) красками.

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

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

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 с.