Отличимость S-лабиринтов

Аннотация

Рассматривается задача об отличимости вершин конечных плоских прямоугольных и s-лабиринтов. Исследуются задачи, аналогичные классическим задачам теории автоматов: отличимости вершин и лабиринтов. Показано, что для изучаемого класса они разрешимы. Найдена оценка длин слов, достаточных для различения вершин лабиринтов. Доказано совпадение отношений изоморфизма и эквивалентности для прямоугольных лабиринтов.

Ключевые слова:

плоский прямоугольный лабиринт, s-лабиринт, отличимость вершин, отличимость лабиринтов.

УДК: 519.713

Abstract

In this paper we consider rectangular and s-labyrinths. We investigate problems similar to classical ones in the automata theory, namely, the distinguishability of vertices and the labyrinths equivalence. We prove that for the considered class of labyrinths these problems are solvable and estimate the distinguishing word length. For rectangular labyrinths we prove that the isomorphism and equivalence relations coincide.

Keywords: plane rectangular labyrinth, s-labyrinth, distinguishability of vertices, distinguishability of labyrinths.

Введение

В настоящее время актуальны задачи, связанные с анализом различных сред с помощью блуждающих по ним агентов (мобильных роботов, автоматов, поисковых программ и т.п.). Агент перемещается по среде, получая при этом некоторую локальную информацию о ней, на основе которой, исходя из некоторой априорной информации, решает поставленные перед ним задачи: например, обходит среду и (или) делает заключения о ее свойствах. В таких задачах рассматриваются различные геометрические модели сред. Однойиз них являются графы, которые можно рассматривать как топологическую модель среды [1]. При анализе графов с помощью блуждающих по ним агентов рассматриваются как обычные графы, так и графы с отмеченными дугами и (или) вершинами. На отмеченных графах естественным образом определяются представимые ими языки в алфавите отметок. В работе [2] описаны различные классы плоских лабиринтов, которые являются частным случаем как графовых, так и автоматных сред. Эти классы вводились многими авторами для решения разных задач. Поэтому интересно исследовать, какие свойства лабиринтов сохраняются и какие изменяются при переходе от класса к классу. В работе [3] исследовались плоские шахматные лабиринты, и для них решались задачи, аналогичные классическим задачам теории автоматов: отличимости вершин и лабиринтов. Было показано, что две вершины шахматного лабиринта с п вершинами неотличимы тогда и только тогда, когда они неотличимы никаким словом длины Щ]. Доказано совпадение отношенийизоморфизма и эквивалентности для шахматных лабиринтов. В даннойработе эти результаты обобщаются на классы прямоугольных лабиринтов и s-лабиринтов. Показано, что оценка длины различающего слова для класса прямоугольных лабиринтов совпадает с оценкой, полученной для шахматных лабиринтов, а при переходе к классу s-лабиринтов она увеличивается в два раза и согласуется как с результатами Мура для конечных автоматов, так и с результатами, полученными для неориентированных графов [4], [5].

Все неопределяемые понятия взяты из [2], [6], [7].

Основные определения Пусть B = {е, n,s,w} – алфавит отметок дуг, 9 – пустойсимвол, B = B U {в}, A .

Отмеченным графом G = (V, Е, а, d) назовем связныйориентированный конечный псевдограф, у которого V– множество вершин, Е – множество дуг, а : v ;V ^ а ; А – функция разметки вершин, d : (v,v') G Е –*¦ d G B — функция разметки дуг. Через |G| обозначим число вершин графа G, а через Aс и Bq – множества отметок всех вершин и дуг графа G соответственно.

Отмеченныйграф G = (V, Е, а, d) назовем симметрическим, если для любых v, v' G V:

1) дуга (v,v') принадлежит Е тогда и только тогда, когда дуга (v',v) принадлежит Е,
2) отметки дуг (v,vr) и (v',v) противоположны [8]. s-лабиринтом L = (V, Е, а, d) назовем симметрическийпланарный граф без петель и кратных ребер, обладающийследующими свойствами:

2.1) отметки b(v, v1) всех дуг, исходящих из вершины v, попарно различны,
2.2) отметка a(v) каждойвершины v есть множество отметок всех исходящих из нее дуг.

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

Прямоугольным лабиринтом назовем s-лабиринт, являющийся прямоугольным графом.

Слово t~l = (ат, d^f_1)(f2, b~9) в алфавите A х B будем называть обратным к слову t = (а, d)(am-i, bm-i)(am, 9). Префиксом длины г (1 < г < t) слова t назовем слово t\i = (а, d) (t, 9). Обозначим длину слова t, т. е. количество букв в нем, через \t\.

Следуя [5], определим на множестве правильных [8] слов частичную операцию 0.

Пусть t = (а, d)(am-i, bm-i)(am, 9), t' = (а'1; b'i)(a,'n_i, b'n_i)(a'n, 9). Тогда положим: t 0 t' = (fli, d)(am-i, 6m_i)(a/1, b'i)(a'n_l, b'n_1)(a'n, 9), t = а't, и t 0 t не определено, если t = а. Обозначим слово t = ton.

Будем обозначать через p(t) маршрут, соответствующий[8] слову t, через Vprt, Epit – множества вершин и дуг этого маршрута соответственно. Пусть слово t соответствует некоторому маршруту с начальнойвершиной v, конечную вершину этого маршрута будем обозначать vt. Через Xv обозначим множество слов, соответствующих всевозможным маршрутам, начинающимся в вершине v.

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

Отмеченныйграф G будем называть детерминированным, если для любойего вершины v каждому слову t из Xv соответствует единственныймаршрут с началом в вершине v. Очевидно, любой s-лабиринт и любойпрямоугольный граф являются детерминированными.

Вершины v отмеченного графа Gиv' отмеченного графа G' назовем неотличимыми, если множества Xv и Xv> совпадают. В противном случае вершины ни»' назовем отличимыми, а слово t G Xv f \vi – различающим. Вершины v отмеченного графа G и v' отмеченного графа G' назовем неотличимыми, если множества слов длины меньшейили равной к из Xv и \vi совпадают. Очевидно, отношения неотличимости и fc-неотличимости являются отношениями эквивалентности.

Отмеченныйграф G назовем приведенным, если любая пара его вершин отличима.

Отмеченные графы G и G' назовем эквивалентными и обозначим G ~ G', если для любой вершины графа G найдется неотличимая от нее вершина графа G' и для любойвершины графа G' найдется неотличимая от нее вершина графа G.

Отмеченные графы G = (V,E,a,b) и G' = (V, Е', а', b1) назовем изоморфными, если существует такое взаимно однозначное соответствие <р> : V —>¦ V, что для любых вершин v,u G V дуга (v,u) принадлежит Е тогда и только тогда, когда ((v),(u)) G Е' и a(v) = a'((v),(u)).

Вершины прямоугольного лабиринта L с отметкой {е, п, w,s} назовем внутренними, все остальные вершины – граничными. Обозначим через Р множество всех простых путей из вершины v лабиринта L в его граничные вершины, а через А^ – множество всех слов, соответствующих всем путям из Р%.

Литература

1. Kuipers B. The spatial semantic hierarchy // Artificial Intelligence. – 2000. – V. 119. – №1–2. – P. 191–233.

2. Килибарда Г. Независимые системы автоматов в лабиринтах // Дискретн. матем. – 2003. – Т. 15. – №2. – С. 3–39.

3. Грунская В.И. Об отличимости плоских шахматных лабиринтов // Интеллектуальные системы. – 2004. – Т. 8. – С. 457–464.

4. Сапунов С.В. Эквивалентность помеченных графов // Тр. ИПММ НАНУ. – 2002. – Т. 7. – C. 162–167.

5. Сапунов С.В. Контроль помеченных графов// Тр. ИПММ НАНУ. – 2003. – Т. 8. – C. 106–110.

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

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

8. Грунская В.И. Реализуемость слов в мозаичных лабиринтах // Известия вузов. Математика. – 2009. – № 8. – С. 1–7.

В.И. Грунская доцент, заведующая кафедрой математики и информатики, филиал Ульяновского государственного университета в г. Димитровграде, 433512, Ульяновская обл., г. Димитровград, пр. Димитрова, д. 4, e-mail: veragrunska@yandex.ru V.I. Grunskaya Associate Professor, Head of the Chair of Mathematics and Information Science, Dimitrovgrad Branch of Ul’yanovsk State University, 4 Dimitrov Ave., Dimitrovgrad, Ul’yanovsk region, 433512 Russia, e-mail: veragrunska@yandex.ru