О поведении автоматов, оставляющих отметки в вершинах лабиринтов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1. Исторический обзор

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

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

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

Первый систематический процесс (алгоритм) для решения собственно задачи о лабиринте, по-видимому, был предложен Винером (С. Wiener) в 1833 году. Другие, более экономичные, способы решения этой же задачи были предложены Тэрри (G. Tarry) и Тремо (Tremaux). Алгоритмы, предложенные этими авторами, по своей сути были схожими с широко известным ныне алгоритмом поиска в глубину в графе.

Первым, кто начал изучать возможности автоматов по обходу лабиринтов, был К. Шеннон. В его работе 1951 года [20] рассматривалась задача поиска автоматом-мышью определенной цели в лабиринте. Модель Шеннона была формализована К. Деппом. В работе [7, 8] в качестве лабиринтов им рассматривались связные конфигурации клеток на плоскости или кубиков в пространстве (так называемые шахматные лабиринты), а в качестве автомата - конечный автомат, который, обозревая некоторую окрестность клетки, в которой находится, может затем перемещаться в соседнюю клетку в одном из координатных направлений. В этой работе было доказано существование для любого конечного автомата трехмерного шахматного лабиринта-ловушки и высказано предположение о существовании такой ловушки на плоскости.

Плоская ловушка для произвольного конечного автомата была построена X. Мюллером [18], но эта ловушка имела вид 3-графа (графа, у которого степени вершин не превышают 3). J1. Будах [5] доказал, что не существует конечного автомата, который обходил бы все плоские шахматные лабиринты. Этот результат был несколько усилен X. Мюллером [19], который заметил, что в качестве ловушки для доказательства теоремы Будаха может быть выбран не более чем 3-связный лабиринт. Оценка сложности такой ловушки была получена X. Антельманом [2], который показал, что количество клеток в ней имеет порядок где т - количество состояний автомата. A.C. Подколзин [30, 31] существенно упростил доказательство Будаха, а Г. Килибарда [26] привел другое доказательство, логически более простое, однако приводящее к более сложной ловушке.

Если же дополнительно потребовать, чтобы автоматы фиксировали факт обхода, то ловушка может быть найдена в значительно более узких классах лабиринтов. Так, например, М. Булл и А. Хеммерлинг [6] доказали, что не существует автомата, который обходит и останавливается после обхода каждого лабиринта из класса всех конечных плоских мозаичных лабиринтов, являющихся деревьями, или из класса всех односвязных конечных плоских шахматных лабиринтов.

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

К. Депп [7, 8] построил автомат, который обходит произвольный конечный плоский односвязный шахматный лабиринт, а Г. Килибарда [25] установил, что минимальное число состояний для такого автомата равно четырем. В той же работе Г. Килибарда описывает еще два класса лабиринтов, для которых удается не только построить универсальные обходящие автоматы, но и получить точные нижние оценки для числа состояний таких автоматов.

В ряде работ были рассмотрены классы лабиринтов с ограничениями на размеры и расположение дыр. А.Н. Зыричев [24] доказал, что класс конечных шахматных лабиринтов, диаметры дыр которых не превосходят заданной константы с?, обходится некоторым автоматом, имеющим не более, чем С(12 состояний. Г. Килибарда [27] понизил эту оценку до Св,, указав при этом, что этот результат останется верным, если вместо шахматных рассматривать мозаичные лабиринты. А.А. Золотых показал, что можно ослабить ограничения, наложенные на размеры дыр. Более точно, в работе [23] он рассматривал класс лабиринтов, внутренние дыры которых ограничены в некотором рациональном направлении константой с? (длина проекции любой дыры на некоторую прямую с рациональным угловым коэффициентом не превосходит с1), и доказал, что для этого класса существует универсальный автомат, число состояний которого линейно зависит от ¿. Кроме того, в той же работе рассматривался случай, когда каждая внутренняя дыра ограничена числом в, хотя бы в одном из некоторого конечного множества рациональных направлений, и для этого случая, при наложении некоторого ограничения на взаимное расположение дыр, построен универсальный обходящий автомат, имеющий не более, чем состоянии.

Второе направление в поисках положительных решений задачи обхода связано с усилением возможностей автоматов. Одно из возможных усилений - рассмотрение систем автоматов. Рассматривались системы двух типов. Первый тип - это так называемые независимые системы автоматов. Поведение в лабиринте каждого автомата из такой системы не зависит ни от положения, ни от состояний других автоматов из этой системы. Поэтому возможности таких систем почти не отличаются от возможностей одного автомата. X. Антельман, Л. Будах и Х.-А. Роллик [1] индукцией по числу автоматов установили существование плоской ловушки для любой конечной независимой системы автоматов, а также построили бесконечную плоскую ловушку сразу для всех автоматов. Другое, не индуктивное, доказательство этого факта получено Ф. Хоффманом [15].

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

М. Блюм и Д. Козен [3] доказали, что существуют коллектив типа (1, 2) и коллектив типа (2, 0), которые обходят произвольный конечный плоский мозаичный лабиринт и останавливаются после обхода. А. Хеммерлинг [11] обобщил этот результат на случай плоских прямоугольных лабиринтов. Ф. Хоффман [15, 16] показал, что коллектив из одного автомата и одного камня не может обойти все плоские мозаичные лабиринты. Однако, класс плоских прямоугольных лабиринтов допускает естественное расслоение такое, что для каждого слоя найдется коллектив типа (1,1), который обходит любой лабиринт из этого слоя. В качестве параметра расслоения берется число дыр лабиринта. В работах К. Кригела и А. Хеммерлинга [10, 12, 17] было доказано, что для любого ^ £ N существует коллектив типа (1,1), обходящий все плоские мозаичные лабиринты, у которых не более к дыр, причем в работах [10, 12] этот результат обобщается на случай ^-связных графов, степени вершин которых не превосходят некоторого числа Ь, но вместо автомата с камнем рассматривается автомат с указателем (указатель отмечает не только вершину, в которой находится, но и одно из входящих в эту вершину ребер).

Задача о нахождении обходящих коллективов, минимальных по числу автоматов и камней, исследовалась и для класса всех конечных и бесконечных плоских мозаичных лабиринтов. М. Блюм и У. Сакода [4] дали эскиз доказательства того, что существует коллектив типа (1,7), обходящий любой лабиринт из этого класса. 3. Хабасинский и М. Карпинский [9] уточнили это доказательство, а А. Шепитовский [21] построил коллектив типа (1,5), решающий ту же задачу. В конструкции А. Шепитовского два камня могут быть заменены одним автоматом. Таким образом, А. Шепитовский, по сути, доказал, что существует коллектив типа (2, 3) (а, значит, и коллективы типов (3,2), (4,1) и (5,0)), обходящий произвольный конечный или бесконечный плоский мозаичный лабиринт. Минимальность этих коллективов была установлена Г. Килибардой [28], который доказал, что для любого коллектива, имеющего один из типов (4,0), (3,1), (2,2) или (1,3), существует бесконечная плоская мозаичная ловушка. Открытой проблемой остался лишь случай коллектива, состоящего из одного автомата и четырех камней.

При рассмотрении лабиринтов более общего вида становится возможным построение ловушек для коллективов автоматов. В работе М. Блюма и У. Сакоды [4] было сформулировано утверждение о существовании конечной трехмерной мозаичной ловушки для любого коллектива автоматов и, для случая, когда все автоматы стартуют из одной вершины, оно было частично обосновано. Полное доказательство этого факта было дано в работе А. Хеммерлинга [13] (см. также [14]), где, для более общего случая старта из произвольного набора вершин, было показано, что для любого коллектива автоматов существует конечная трехмерная мозаичная ловушка, лежащая в двух параллельных плоскостях. Г. Килибарда и Ш. Ушчумлич [29] построили бесконечную трехмерную ловушку сразу для всех коллективов автоматов, причем каждый коллектив не выходит в этой ловушке за пределы некоторого шара, радиус которого зависит от конкретного коллектива.

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

2. Структура и краткое содержание диссертации

Диссертация состоит из введения, двух глав, каждая из которых разбита на пять параграфов, и списка литературы.

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

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

Через Т>2 = {е, п, б} обозначим множество отметок дуг плоских прямоугольных лабиринтов.

Определение. Автомат 21 — (А, ф, В, ф) называется автоматом с к красками, оставляющим след (или, короче, автоматом с /¿-следом), к € если А = {0,1,., к} х Ро(В2) - входной, В = {1,., к} х Т)2 ~ выходной алфавиты, (риф- функции переходов и выходов, а множество состояний С} представимо в виде = С}х и и . и С^к, где П = 0 при р ф г, причем для любых д £ С}, а Е А я для любых г, ^ € 1, к выполнено:

1) Пр2(^(д, а)) € Пр2(а),

2) если и (р(д, а) е С^^, то г < ] и Пр1(^(д, а)) = у.

Пусть 21до - инициальный автомат с ^-следом, ЬУо - инициальный плоский прямоугольный лабиринт, вершины которого могут быть помечены символами из множества 0, к. Функционирование автомата 21?о в лабиринте понимаем следующим образом. В начальный момент времени автомат Я1до помещается в вершину у0 в состоянии д0, отметки всех вершин изначально равны 0 (вершины неокрашены). Автомат перемещается по лабиринту, оставляя в вершинах лабиринта отметки из множества 1, к (след). Пусть в момент времени £ автомат находился в вершине V в состоянии д (Е Тогда входной буквой автомата в этот момент времени будет пара а = (а;, [г;]), где и - отметка вершины V, а [г;] - множество отметок дуг, выходящих из v. Если ф(д,а) = е), то автомат ставит отметку 3 в вершину v, перемещается в вершину, в которую из v ведет дуга с отметкой е, и переходит в состояние (р(д,а) (Е Qj, "запоминая", тем самым, отметку, поставленную в момент времени Так как ] ^ 1, то автомат 01Яо ставит в каждую пройденную вершину ненулевую отметку (окрашивает вершину), а из условия ъ ^ ] следует, что с течением времени отметки, оставляемые автоматом, (номера красок) неубывают, а могут лишь возрастать, не превышая числа к.

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

В §2 рассмотрены два случая положительного решения задачи обхода бесконечных лабиринтов автоматами со следом. Построены автоматы 21 и 2{.£3, обходящие плоскость (лабиринт и пространство (лабиринт Zз), соответственно.

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

Определение. Конечный правильный плоский прямоугольный лабиринт Щ = (V, Г) с выделенной вершиной и Е V такой, что с^(-и) = 1 и {и,у0) С Г, называется возвращающим для автомата без печати, если

Щ(Уг = уе) ^((1 = У0У Vз = и)), где (д0, у0), VI), {$2, иг), ■ • • - поведение автомата 519о в

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

В §4 приведено доказательство теоремы об автомате с £;-следом, а в пятом параграфе показано, что для любого автомата с /с-следом можно построить мозаичную и шахматную бесконечные трехмерные ловушки.

Утверждение. Для любого автомата с к-следом существуют:

1) бесконечная трехмерная мозаичная ловушка, лежащая в двух плоскостях г = 0 и г = 1,

2) бесконечная трехмерная шахматная ловушка, лежащая в трех плоскостях г = 0,г = 1иг = 2, причем эти ловушки имеют лишь конечное число вершин вне плоскости 2 = 0.

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

В §6 даны определения автомата с к красками и п-мерного прямоугольного лабиринта, там же сформулирован основной результат главы 2 - теорема об автомате с одной краской.

Обозначим класс всех п-мерных прямоугольных лабиринтов через Сп, а через Еп = {е\,., еп, ёх,., ёп} обозначим множество отметок дуг этих лабиринтов.

Определение. Конечный автомат 21 = (А, <2, В,ср,ф) называется авто матом с к красками, допустимым для класса Сп, где & Е 14, если А — {0,1,.,к}х Р0{£п) - входной алфавит, В = {0,1,., к} х (£п и {Л}) - выходной алфавит, а функция выходов ф такова, что для любых q £ а Е А выполнено:

1) Пр2(^,а))бПр2(а)и{Л},

2) если Прх(а) > 0, то Пр1(^(^,а)) = Прх(а).

Пусть - некоторый инициальный автомат с к красками, ЬУо - инициальный п-мерный прямоугольный лабиринт, вершины которого могут быть помечены символами из О, А;. Функционирование автомата %Яо в лабиринте ЬУо понимаем следующим образом. В каждый момент времени автомат обозревает какую-то из вершин лабиринта. Пусть автомат находится в состоянии д и обозревает вершину у лабиринта. Тогда входной буквой автомата в этот момент времени будет пара а = (и, [г?]), где ш - отметка вершины у. Если ф(д,а) = (о/, е), то автомат ставит отметку ш' в вершину у, переходит в состояние ср(д, а) и перемещается в вершину, в которую из у ведет дуга с отметкой е (если е = Л, то автомат остается в вершине у). При этом, если и > 0 (вершина у окрашена), то а/ = ш (отметки нестираемы). В начальный момент автомат находится в состоянии (¡а и обозревает вершину у0.

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

В §7 изучаются свойства равнонаправленных лабиринтов.

Определение. Лабиринт Ь — (V, Г) с множеством отметок дуг Еп называется равнонаправленным (рн-лабиринтом), если

1) Ь - сильносвязный ориентированный граф,

2) для любой вершины v £ V множество отметок входящих в вершину V дуг и множество отметок выходящих из V дуг совпадают.

Отметим некоторые из результатов этого параграфа.

1. Для каждого п-мерного прямоугольного лабиринта построен рн-лабиринт с тем же множеством вершин (порожденный рн-лабиринт).

2. Построены автоматы без печати, которые, перемещаясь по п-мерному прямоугольному лабиринту, моделируют перемещения по дугам порожденного рн-лабиринта.

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

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

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

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

§8.

Наконец, в

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

Утверждение. Для любого п 6 N существует автомат с одной краской, имеющий 5п5 + 0(п4) состояний, который обходит произвольный конечный п-мерный прямоугольный лабиринт и останавливается после обхода.

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

Обозначим через С^ класс всех конечных прямоугольных лабиринтов, а через - множество отметок дуг этих лабиринтов: оо оо

-^оо = U = U & ■

71=1 П=

Определение. Автомат 21 = (А, Q, В, tp, ф) называется автоматом с к красками, допустимым для класса Сс0, если А = {0,1,., k} х входной алфавит, В = {0,1,., к} х U {А}) - выходной алфавит, Q -конечный алфавит состояний, а функция выходов ф такова, что для любых q € Q, a G А выполнено:

1) Пр2(^(д,а)) еПр2(а)и{Л},

2) если Пр1(а) > 0, то Пра)) = Пр^а), где через Р/¿n(£°°) обозначено множество всех конечных непустых подмножеств множества £°°.

Утверждение. Не существует автомата с к красками, допустимого для класса Cœ, который обходит произвольный лабиринт из класса

Благодарности

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

Автор благодарен академику РАЕН и АТН РФ В.Б. Кудрявцеву и всему коллективу кафедры математической теории интеллектуальных систем за постоянную поддержку и внимательное отношение к данной работе.

Глава

§1. Автоматы в лабиринтах, основные понятия

Основные понятия и обозначения из теории автоматов и теории графов, которыми мы будем пользоваться, совпадают с принятыми в [30] и [32], соответственно, и здесь не определяются.

Пусть X - некоторое множество. Через РоРО обозначим множество всех непустых подмножеств множества X, а через |Х| - мощность множества X. Пусть {Ха}аеА ~ некоторое индексированное семейство множеств. Тогда для любого а £ А через Пра обозначим отображение проектирования произведения на его а-й сомножитель Ха. Если множество индексов А конечно, то будем полагать, что А — {1,., |Л|}. Множество Z П [а; Ь] будем обозначать а, Ъ.

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

Пусть Ь — (V, Г) - связный ориентированный граф, не имеющий петель и кратных дуг; V - множество вершин, Г - множество дуг графа Ь. Если в графе Ь = (V, Г) вместе с дугой (г>1,г>2) содержится дуга (г^,^), то эту пару дуг называем ребром и обозначаем , ^2) - Граф Ь = (У, Г) называется симметрическим, если для любой дуги (г^; 1*2) € Г имеет место (у\, г^) С Г.

Если всем дугам графа Ь — (V, Г) приписаны отметки из некоторого алфавита £ таким образом, что разным дугам, исходящим из одной и той же вершины, приписаны разные отметки, то этот нагруженный граф называем лабиринтом. Отметку дуги 7 € Г обозначим через ¡7|. Часто мы будем рассматривать лабиринты, у которых выделена одна вершина v0 или две вершины vQ и г>е; при этом, v0 будем называть начальной вершиной (входом), a ve - конечной вершиной (выходом). Лабиринт L с выделенными вершинами vQ или v0 и ve называется инициальным и обозначается LVo или LVojVe, соответственно. Для любой вершины v лабиринта L = О^Г) введем обозначения: v[l - множество отметок дуг, входящих в вершину v, ['v]l - множество отметок дуг, выходящих из вершины v. Если из контекста ясно, о каком лабиринте идет речь, то будем писать ]г>[ и [г>], соответственно.

В этой главе мы будем рассматривать преимущественно прямоугольные лабиринты. В таких лабиринтах в качестве отметок для дуг берутся символы из множества D2 = {е, n, w, s} или D3 = D2 U {u, d} (здесь е, n, w, s, и, d - начальные буквы слов east, north, west, south, up, down). Положим е-1 = w, n"1 = s, w1 — e, s1 = n, u"1 = d, d1 = u.

Пусть ЖЙ = xi + yj + zk, где M и N, M ф N, - некоторые точки пространства, а г, j и k - единичные координатные векторы прямоугольной системы координат в пространстве. Будем считать (см. рис. 1), что отрезок MN идет в направлении е, если х > 0, у = 0 и г = 0, w, если х<0, у = 0 и г = О, и, если х = 0, у > 0 и z = 0, s, если x = 0,y<0nz = 0, и, если х = 0, у = 0 и г > 0, d, если ж = 0, i/ = 0nz<0.

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

Лабиринт Ь = (У, Г) с множеством отметок дуг называется трехмерным прямоугольным лабиринтом, если

1) Ь - связный симметрический граф,

2) V С БД

3) для любой дуги (и,у) £ Г отрезок Ш идет в направлении \(и,у)\,

4) множество отрезков Т = {ш | (и, у) € Г} является конфигурацией. Через (или с^(г>), если ясно, какой лабиринт имеется ввиду) будем обозначать количество ребер, входящих в вершину у трехмерного прямоугольного лабиринта Ь. Поскольку прямоугольный лабиринт является но, при этом, симметрическим графом, то для него degL(v) = ]у[ь часто ]у[ь^ [у]ь

Пусть Z3 - целочисленная решетка в К3. Трехмерный прямоугольный лабиринт Ь = (V,, Г) называется трехмерным мозаичным лабиринтом, если У С г3 и Т = {ш; | (и, у) € Г} - множество отрезков длины 1. Если, при этом, в лабиринте Ь любые вершины, находящиеся друг от друга на расстоянии 1, соединены ребром, то такой мозаичный лабиринт называется трехмерным шахматным лабиринтом. На рис. 2 приведены примеры трехмерного прямоугольного (а), мозаичного (б) и шахматного (в) лабиринтов.

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

Если в трехмерном прямоугольном (мозаичном, шахматном) лабиринте нет дуг с отметками и и с1, то этот лабиринт расположен в одной плоскости; без ограничения общности можно считать, что это плоскость хОу. Такие лабиринты называются плоскими прямоугольными (мозаичными, шахматными) лабиринтами. Множеством отметок дуг плоских лабиринтов является множество Т>2 и можно считать, что плоские лабиринты вложены в И,2.

Класс всех трехмерных прямоугольных лабиринтов обозначим через £3, а класс всех плоских прямоугольных лабиринтов через С2.

Пусть Ь — {V, Г) - некоторый плоский прямоугольный лабиринт. Фигура

Ь = и ш; (и,г/)ег в Я2 называется реализацией лабиринта Ь. Плоский прямоугольный лабиринт Ьуо:уе называется правильным, если существует бесконечный плоский прямоугольный лабиринт Ь\ такой, что Ь П Ь\ = {уе} и фигура Ь\ является неограниченной. На содержательном уровне "правильность" лабиринта означает, что выход из него осуществляется во внешнюю область.

Пусть ЬУо^е — (V, Г) - некоторый лабиринт. Если существует изоморфный Ь плоский прямоугольный лабиринт Ь'у,у = (V, Г7), то говорят, что Ь вложим, а задаваемое этим изоморфизмом отображение /л : V —> V' называется укладкой лабиринта Ь. Если при этом лабиринт V правильный, то Ь называем правильно вложимым, ад- правильной укладкой. Ясно, что отображение д однозначно задает Ь', поэтому, под укладкой будем иногда понимать V или даже Ь'.

Определим теперь класс автоматов, которые могут "перемещаться" по прямоугольным лабиринтам.

Определение 1. Конечный автомат 21 = (Л, В, (р, ф) называется допустимым для класса С^ где г = 2, 3, если А = Ро(В«) - входной алфавит,

В = Юг и {Л} - выходной алфавит, - алфавит состояний, (р - функция переходов, а функция выходов ф такова, что для любых д £ С} ж а £ А выполнено ф(д, а) Е а и {Л}.

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

Пусть 219о - автомат с начальным состоянием д0, допустимый для класса С2 (£3), ЬУо - инициальный плоский (трехмерный) прямоугольный лабиринт. Функционирование автомата в лабиринте ЬУо происходит в дискретном времени £ = 0,1,2,— В каждый момент времени t автомат обозревает какую-нибудь вершину лабиринта. Предположим, что в момент времени £ автомат находился в состоянии д £ С} и обозревал вершину V. Тогда входной буквой автомата в этот момент времени будет а = [г>] - набор из отметок дуг, выходящих из V. Состояние автомата и обозреваемая вершина в момент времени 1 + 1 определяются следующим образом. Если ф(д,а) ф А, то автомат перемещается в вершину, в которую из у ведет дуга с отметкой ф(д,а) (такая дуга всегда найдется, поскольку ф(д,а) Е а), а если ф(д, а) = А, то автомат остается в вершине г>, и, в любом случае, переходит в состояние ср(д, а). В начальный момент времени автомат помещается в вершину у0 в состоянии д0.

Формально функционирование автомата в лабиринте определяется через понятия конфигурации и поведения.

Конфигурацией инициального автомата = (А, ф, В, ср, ф, д0), допустимого для класса £2 (£3) в плоском (трехмерном) прямоугольном лабиринте ЬЬо = (V, Г) называется пара К = (д, у), где д Е ф и V Е V. Конфигурация (д0, у0) называется начальной.

Если д' = (р(д, [г?]) и, либо ф(д, [у]) = X ж у' = у, либо ф(д, [г>]) ф А и (у;у') Е Г, причем |(г>;г/)| = ф(д, [у]), то говорят, что конфигурация (д', у') следует за конфигурацией (д,у) и обозначают (д,у) Ь (д':у').

Несколько следующих определений будут общими для всех классов автоматов и лабиринтов, рассматриваемых в данной диссертации.

Поведением автомата 219о в лабиринте ЬУо = (V, Г) называется последовательность 7г(21до, Ьуо) конфигураций Ко, К\, К2, ■ ■ ■ таких, что Ко - начальная конфигурация и К{ К{+\ для всех г ^ 0. Пусть У1 С У, тогда У\-поведением назовем подпоследовательность К{0, К^, К{2,. поведения 7г(21 Яо,Ьуо), которая получается из 7г(219о, ЬУо) удалением всех конфигураций К, у которых вершина Пр2(.КТ) не принадлежит

Пусть 7г(21до, ЬУо) = Ко, К2,Рассмотрим

- множество всех вершин, которых обходит автомат 219о в лабиринте ЬУо.

Инициальный автомат 21до обходит инициальный лабиринт ЬУо = (У, Г), если Ьуо) = V. Если в лабиринте Ь выделена не только начальная, но и конечная вершина уе, и уе Е 1гй(21 Чо,Ьуо^е), то говорят, что автомат %Чо выходит из лабиринта Если автомат не обходит лабиринт ЬУо не выходит из Ьуо^е), то говорят, что Ьуо (ЬУо^е) является ловушкой для автомата 01Яо.

Как уже отмечалось, Л. Будах [5] доказал, что для любого автомата, допустимого для класса С2, существует конечная плоская шахматная ловушка. В связи с этим возник вопрос об изучении различных усилений моделей автомата, решающих задачу обхода лабиринтов.

В качестве одного из таких усилений в этой главе будут рассмотрены автоматы, "принудительно" оставляющие отметку 1 (след) в вершинах лабиринта. Таким образом, такие автоматы получают возможность отличать еще не пройденные вершины, от вершин, в которых уже побывали. Естественным обобщением этого класса автоматов являются автоматы, которые оставляют в каждой пройденной вершине отметки из множества {1,2При этом, нетривиальным является лишь тот случай, когда номер (цвет) оставляемой отметки неубывает в процессе обхода. Такой подход требует от автомата "запоминания" отметки, оставленной в предыдущий момент времени. Как правило, это означает, что множество состояний автомата распадается на к подмножеств, каждое из которых соответствует определенному номеру отметки.

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

Определение 2. Автомат 21 = (А, С}, В, </?, ф) называется автоматом с к красками, оставляющим след (или, короче, автоматом с ^-следом), к Е К, если А = {0,1,., к} х Ро(Ог) - входной, В = {1,., к} х Ю2 - выходной алфавиты, и ф - функции переходов и выходов, а множество состояний (5 представимо в виде = I) (^2 и . и где С}г = 0 при р ф г, причем для любых д £ <5, а 6 Л и для любых г, з £ 1 ,к выполнено:

1) Пр2(^(д,а)) еПр2(а),

2) если д Е и а) £ то г ^ з и Пр1(^(д, а)) = j.

При & = 1 вместо выражения "автомат с 1-следом" будем писать "автомат со следом".

Поскольку автоматы с /^-следом обладают способностью оставлять отметки в вершинах лабиринтов, то понятия функционирования и конфигурации претерпевают определенные изменения по сравнению с аналогичными понятиями для автоматов без печати. Как и определение автомата с к-следом, мы сформулируем эти понятия только для случая плоских прямоугольных лабиринтов.

Пусть 219о - инициальный автомат с А:-следом, ЬУо - инициальный плоский прямоугольный лабиринт, вершины которого могут быть помечены символами из множества 0, к. Функционирование автомата 219о в лабиринте ЬУо понимаем следующим образом. В начальный момент времени автомат помещается в вершину у0 в состоянии д0, отметки всех вершин изначально равны 0 (вершины неокрашены). Автомат перемещается по лабиринту, оставляя в вершинах лабиринта отметки из множества 1, к (след). Пусть в момент времени t автомат находился в вершине у в состоянии q ^ Qi. Тогда входной буквой автомата в этот момент времени будет пара а = (а[г;]), где и - отметка вершины у. Если ф(д,а) — (з, е), то автомат ставит отметку з в вершину у, перемещается в вершину, в которую из у ведет дуга с отметкой е, и переходит в состояние (р(д,а) £ "запоминая", тем самым, отметку, поставленную в момент времени Так как ^ ^ 1, то автомат %1о ставит в каждую пройденную вершину ненулевую отметку (окрашивает вершину), а из условия г ^ ] следует, что с течением времени отметки, оставляемые автоматом, (номера красок) неубывают, а могут лишь возрастать, не превышая числа к.

Конфигурацией инициального автомата = (А, (¡), В, ф) с следом в плоском прямоугольном лабиринте ЬУо = (V, Г) называется тройка К = (д,г>,Г2), где д £ V £ V, а £1 : V —>• {0,1., к} - разметка лабиринта, то есть 0,(у) - отметка вершины V. Конфигурация (д0:Уо^о)^ где П0 = О, называется начальной.

Говорят, что конфигурация (д',у', ГУ) следует за конфигурацией (д, V, £1) и обозначают (д, у, Г2) (д', у', О,'), если где а = (Г2(г;), [г;]).

Понятия поведения, автомата, обходящего лабиринт, и ловушки для автоматов с ^-следом будут такими же, как и для автоматов без печати.

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

Теорема 1 (об автомате с /¿-следом). Не существует автомата с к-следом, который обходит произвольный бесконечный плоский прямоугольный лабиринт.

Прежде, чем приступить к доказательству этой теоремы, мы рассмотрим два случая положительного решения задачи обхода бесконечных лабиринтов автоматами с к-следом. д' == (р(д, а), (у, у') £ Г, |(г;; у')\ = 11р2(ф(д, а)) ч и?1тЯ>а )1 если и = а (и) — <

2. Обход плоскости и пространства автоматами со следом

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

Обозначим через Z3 трехмерный шахматный лабиринт, множество вершин которого совпадает с Z3, а через Z<i плоский шахматный лабиринт, у которого множество вершин совпадает с Z2.

A.B. Анджанс [22] показал, что не существует коллективов типа (1,2) и (2,0), обходящих лабиринт но существуют коллективы типов (1, 3) и (2,1), которые обходят этот лабиринт.

Основная причина того, что " малые" коллективы автоматов не обходят плоскость, - "однородность" лабиринта Z2. Это можно показать на примере одного автомата. Поместим некоторый конечный автомат в произвольную вершину лабиринта Zi- Из бесконечности Z<x следует, что найдутся моменты времени t\ и ¿2; в которые этот автомат находится в одном и том же состоянии q. Тогда, в моменты времени ti = ti + (i — 1) (¿2 — ¿1) автомат также находится в состоянии д, попадая в вершины г>г-, определяемые условием v\i)i = (г — l)v\v\. Значит, автомат не выходит за пределы некоторой полосы, параллельной вектору щу2, и, следовательно, не обходит лабиринт

Автоматы со следом, оставляя отметки в пройденных вершинах, разрушают однородность лабиринтов Zi и Z3. Благодаря этому, удается построить автоматы со следом 21 z2 и 21 которые, постепенно расширяя область пройденных вершин, обходят лабиринты Zi и Z3, соответственно.

Опишем сперва автомат 21 . Поскольку все вершины лабиринта Z<± имеют одинаковые наборы выходящих дуг, то можно считать, что на вход автомата 2{.£2 подается только отметка текущей вершины. Кроме того, по определению автомата со следом, такой автомат оставляет в каждой пройденной вершине отметку 1, а, значит, можно считать, что на выходе автомат 21^2 выдает только направление из множества D2.

На рис. 3 изображена диаграмма Мура автомата 21 На диаграмме использованы следующие обозначения. Рядом с каждой стрелкой, соответствующей переходу между состояниями, стоит дробь. В числителе дроби записан входной символ (отметка вершины), при котором происходит этот переход, а в знаменателе - получающийся на выходе автомата символ из множества Ю2 (направление перемещения автомата). Звездочкой отмечено начальное состояние автомата 21^ •

Заметим, что задаваемый этой диаграммой автомат является частичным, так как его функции переходов и выходов неопределены для состояния qw и входной отметки 1. Но, при необходимости, он может быть доопределен произвольным образом и это не изменит его поведения в лабиринте Z2.

Далее, для краткости, вместо "вершина лабиринта ^2, имеющая координаты х и у" будем писать "вершина (х; у)". Поместим 21^2 в произвольную вершину лабиринта Без ограничения общности, можно считать, что это вершина (0; 0). Поведение автомата 21 в лабиринте ¿72, согласно приведенной выше диаграмме, можно условно разбить на "циклы". При завершении п-ного цикла множество вершин, пройденных автоматом 21^2, будет совпадать с множеством Мп = {{х,у) | — (п — 1) ^ж + у^п + 1; — п ^ х — у ^ п}, см. рис. 4.

11 | •

0 1 X

2(1 • • о • • тг* •

• • • •

• • 11 • ''-о+ !

• • • •

Первый цикл автомат начинает в вершине (0; 0) в состоянии qs. Поскольку в начальный момент вершины лабиринта неокрашены, то автомат 21 последовательно переместившись в направлениях е, п и XV, см. рис. 5(а), попадет в вершину (0; 1) в состоянии В этот момент все вершины из множества М\ пройдены и первый цикл закончен. Далее, при г ^ 2, каждый г-тый цикл автомат 21^2 начинает в неокрашенной вершине (0; г — 1) в состоянии qlJ и заканчивает в том же состоянии в вершине (0;г). Перемещения, составляющие второй цикл, показаны стрелками на рис. 5(6). Вершины, имевшие на момент начала второго цикла отметку 1, изображены закрашенными кружочками, а остальные вершины - пустыми кружочками.

0 1 X лТЧ tj>-<-« i •

-»-в • f-*-i> о-»ч i •-•<> 1-1 Q-wi

В общем случае, как было уже указано, г-тый цикл автомат 21^2 начинает в неокрашенной вершине (0;г — 1) в состоянии и, к этому моменту времени, пройденными будут только вершины из множества i. В следующий момент времени он переходит в состояние qw и перемещается в вершину (—1; г — 1). Эта вершина не принадлежит множеству M¿i и, следовательно, еще не окрашена. Поэтому, 21^2 переместится в направлении s в вершину (—1; г — 2) и перейдет в состояние qs. Вершина (—1; г — 2) принадлежит множеству Mi-\ и, значит, уже окрашена. Отсюда следует, что в следующий момент времени автомат 21 z2 вернется в состояние qw и переместится в направлении w. Такое чередование состояний qs и qw будет продолжаться до тех пор, пока 21 не окажется в состоянии qs в вершине г — 1); 0). Затем, он перейдет в состояние де и переместится в окрашенную вершину (—(г — 2);0). Далее, чередуя состояния д5 и де, автомат 21^2 попадет в состоянии де в вершину (1; — (г — 1)). Таким же образом, чередуя перемещения в направлениях п и е, 21^2 окажется в вершине (г; 1) в состоянии дп. Наконец, перемещаясь поочередно в направлениях и п, автомат попадет в вершину (0; г) в состоянии д^. На этом г-тый цикл закончен, все вершины из множества М{ пройдены и начинается (г + 1)-ый цикл. Перемещения, соответствующие г-тому циклу, показаны на рис. 5(в).

Поскольку объединение множеств Мп совпадает с Z2, то автомат 21^2 обходит лабиринт

Опишем теперь автомат 21^3. Также, как и в случае автомата 21^2, можно считать, что на вход автомата 21^3 подается только отметка текущей вершины, а на выходе 21^3 выдает направление из множества Оз. Диаграмма Мура автомата изображена на рис. 6.

1/е о/е

Автомат 21^3, задаваемый этой диаграммой, является частичным: в состояниях д^ и не определены переходы при входной отметке 0, в состояниях д^, д*, д^ - при отметке 1. Это позволяет, отождествив состояние д^ с д2 и состояние д;? с д^, сократить число состояний автомата до 15. В состояниях дш и автомат 21 доопределяется произвольным образом.

Обозначим через Тп множество

Тп = мг1 и м2п-2 и. и и М"1 и М"2! и. и м^, где М^ = {(ж, у, г) | — (п — 1) ^ ж + у ^ п + 1; —п ^ £ — у ^ п; = Заметим, что проекция на плоскость хОу совпадает с ранее введенным множеством Мп.

Поместим автомат 21 ^ в вершину (0; 0; 0) лабиринта Поведение автомата 21^3 в лабиринте Z^>) условно разбивается на циклы так, что при завершении п-ного цикла оказываются пройденными все вершины из множества Тп.

Первый цикл автомат 21^3 начинает в неокрашенной вершине (0; 0; 0) в состоянии и после перемещений в направлениях е,п,\у,с1,е,8,\у, см. рис. 7(а), обходит все вершины из оказываясь в неокрашенной вершине (0; 0; —1) в состоянии

О-щ •-♦О Си-* (I • ¿-»О к-г (>«

Каждый следующий г-тый цикл автомат 21^3 начинает в неокрашенной вершине (0; 0; 1 — г) в состоянии и заканчивает в неокрашенной вершине (0; 0; —г) в том же состоянии. Цикл разобьем на два этапа.

В начале первого этапа 21^3 перейдет из состояния в состояние qu и переместится в направлении и в вершину (0; 0; 2 — г). Далее, оставаясь в состоянии qu, автомат 21^3 будет перемещаться вдоль оси О г в направлении и до тех пор, пока не достигнет неокрашенной вершины (0; 0; г — 1).

После этого, сделав последовательно перемещения в направлениях е,пи¥, автомат 21^, попадет в неокрашенную вершину (0; 1; г — 1) в состоянии д^. Заметим, что на этот момент времени пройденные автоматом 21^3 вершины образуют в плоскости х — г — \ множество М]-1, а в плоскости г = г — 2 -множество М{~2. Поэтому, переместившись в направлении <1, автомат попадет в закрашенную вершину (0; 1;г — 2) в состоянии q¿. Далее, находясь в плоскости г = г — 2, автомат будет действовать также, как и пока не окажется в состоянии в незакрашенной вершине (0;2;г — 2), а множество пройденных вершин в плоскости 2 = г — 2 к этому моменту увеличится до Затем, автомат перейдет в состояние д^ и переместится в направлении (1 в плоскость 2 = г — 3. Если вершина (0; 2; г — 3), в которой он окажется, будет закрашенной, то автомат 21^3 опять начинает действовать также, как и автомат В общем случае, если 21 оказался в вершине (0; к — 1; г — к) в состоянии д^ и эта вершина имеет отметку 1, то это означает, что в плоскости г = г — к пройденные вершины образуют множество Мгк и автомат 2Ц,, используя состояния дш, д5, де, дп и д^, начинает действовать также, как и 21 В результате, он увеличивает множество пройденных вершин в этой плоскости до Мгк~к и перемещается в плоскость г = г — к — 1, оказываясь в состоянии д^ в вершине (0; г — к — 1). Этот процесс последовательного увеличения множества пройденных вершин в плоскостях вида г — % — к будет продолжаться, пока автомат не попадет в состоянии д^ в незакрашенную вершину. Это произойдет, когда 21^3 окажется в вершине (0;г; —1) - это начало второго этапа. Множество всех пройденных автоматом 21 вершин к этому моменту времени будет состоять из множеств М{~1, ., М?, М~}ъ М~}ъ ., М\~г.

На втором этапе автомат 21^3 продолжает спуск вниз, он поочередно проходит через плоскости г = —1, г = —2, г = —г ив каждой из плоскостей расширяет до необходимых размеров множество пройденных вершин. В общем случае это происходит следующим образом. Свои перемещения в плоскости г = —к (к Е 1, г — 1) автомат 21^3 начинает в состоянии д^ из вершины (0; г — к + 1; —к), см. рис. 7(6). При к ^ г — 1 в плоскости г = —к уже есть пройденные ранее вершины - это вершины из множества

Поэтому, после перемещений в направлениях еи з автомат оказывается в состоянии в закрашенной вершине (1; г — к; —к). Далее, чередуя состояния ^ и он попадает в незакрашенную вершину (г — к + 1; 0; —к) в состоянии ql. После этого, чередуя сначала состояния и а затем и автомат 21 оказывается в незакрашенной вершине (к — г; 1; —к) в состоянии Наконец, чередуя перемещения в направлениях е и п, автомат возвращается в состоянии в уже закрашенную вершину (0; г — к + 1; —к). В этот момент времени все вершины из множества М^к+1 оказываются пройденными, и, сделав перемещения в направлениях бис!, автомат 21^3 в состоянии qd попадает в вершину (0; г — к;— к — 1) на плоскости г = —к — 1.

Расширив, таким образом, множества пройденных вершин в плоскостях 2 = — 1, г = — г + 1 до множеств Мгг1, ., М2~\ соответственно, автомат 21^з в состоянии оказывается в вершине (0; 1; —г), принадлежащей плоскости г = —г. В этой плоскости еще нет окрашенных вершин, поэтому перемещениями в направлениях е, в и автомат 21 обходит множество М-р, завершая этот обход в вершине (0; 0; —г) в состоянии На этом обход множества Т^ завершен и г-тый цикл закончен.

1. Antelmaim H., Budach L., Rollik H.-A. On universal traps // Electronische 1.formationsverarbeitung und Kybernetik. - 1979. - V.15, №3. - P. 123 -131.

2. Antelmann H. An application of the prime number theorem in automata theory // ICS PAS Reports 411. 1980. - P. 9 - 11.

3. Blum M., Kozen D. On the power of compass // The Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978. -P. 132 - 142.

4. Blum M., Sakoda W. On the capability of finite automata in 2 and 3 dimensional space // The Proceedings of the 18th Annual Symposium on Foundations of Computer Science. 1977. - P. 147 - 161.

5. Budach L. Automata and labyrinths // Math. Nachrichten 86. 1978. -P. 195 - 282.

6. Bull M., Hemmerling A. Finite embedded trees and simply connected mazes cannot be searched by halting finite automata // Journal of Inf. Process and Cyber. EIK. 1990. - V.26, №1,2. - P. 65 - 73.

7. Döpp K. Automaten in labirinthen I // Electronische Informationsverarbeitung und Kybernetik. 1971. - V.7, №2. - P. 79 - 94.

8. Döpp K. Automaten in labirinthen II // Electronische Informationsverarbeitung und Kybernetik. 1971. - V.7, №3. - P. 167 - 190.

9. Habasinski Z., Karpinski M. A codification of Blum-Sakoda 7-pebbles algorithm // ICS PAS Reports 448.- 1981.

10. Hemmerling A., Kriegel K. On searching of special classes of mazes and finite embedded graphs // Lecture Notes in Computer Science. 1984. -V.176. - P. 291 - 300.

11. Hemmerling A. Remark on the power of compass // Lecture Notes in Computer Science. 1986. - V.233. - P. 405 - 413.

12. Hemmerling A. 1-Pointer automata searching finite plane graphs // Z.Math. Logik Grundlag. Math. 1986. - B.32. - S. 245 - 256.

13. Hemmerling A. Normed two-plane traps for finite systems of cooperating compass automata // J. Inf. Process Cybern. EIK 1987. - V.28, №8,9. -P. 453 - 470.

14. Hemmerling A. Three-dimensional traps and barrages for cooperating automata // Lecture Notes in Computer Science. 1987. - V.278. - P. 197- 203.

15. Hoffman F. One pebble does not suffice to search planar labyrinths // Lecture Notes in Computer Science. 1981. - V.117. - P. 433 - 444.

16. Hoffman F. 1-Kiesel-Automaten in Labyrithen // Report R-Math-06/82.- 1982. AdW der DDR, Berlin.

17. Kriegel K. Universelle 1-Kiesel-Automaten für &-komponentige Labyrithe // Report R-Math-04/84. 1984. - AdW der DDR, Berlin.

18. Müller H. Endliche Automaten und Labyrinthe // EIK 1971. - V.7, №4.-P. 261 - 264.

19. Müller H. Automata catching labyrinths with at most three components // EIK 1979. - V.15, №1,2. - P. 3 - 9.

20. Shannon CLE. Presentation of a maze-solving machine // Cybernetics Trans, of the 8th Conf. of the Josiah Macy Jr. Found. 1951. - P. 173-180.

21. Szepietowski A. A finite 5-pebble automaton can search every maze // Information Processing Letters. 1982. - V.15, №5. - P. 199 - 204.

22. Анджанс A.B. Поведение детерминированных и вероятностных автоматов в лабиринтах: Дис. канд. физ.-мат. наук. Рига, 1987. - 90 с.

23. Золотых A.A. Обход лабиринтов с ограниченными в фиксированных направлениях дырами // Дискретная математика. 1993. - Т.5, вып. 1.- С. 59 69.

24. Зыричев А.Н. О синтезе автомата, обходящего плоские лабиринты с ограниченными дырами // Дискретная математика. 1991. - Т.З, вып. 1. - С. 105 - 113.

25. Килибарда Г. Об универсальных лабиринтах-ловушках для конечных множеств автоматов // Дискретная математика. 1990. - Т.2, вып. 1.- С. 72 79.

26. Килибарда Г. Новое доказательство теоремы Будаха-Подколзина // Дискретная математика. 1991. - Т.З, вып. 3. - С. 135 - 146.

27. Килибарда Г. О сложности автоматного обхода лабиринтов // Дискретная математика. 1993. - Т.5, вып. 3. - С. 116 - 124.

28. Килибарда Г. О минимальных универсальных коллективах автоматов для плоских лабиринтов // Дискретная математика. 1994. - Т.6, вып. 4. - С. 133 - 153.

29. Килибарда Г., Ушчумлич Ш. О лабиринтах-ловушках для коллективов автоматов // Дискретная математика. 1993. - Т.5, вып. 2. - С. 29 -50.

30. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М.: Наука, 1985.

31. Кудрявцев В.Б., Подколзин A.C., Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Изд-во МГУ, 1985.

32. Харари Ф. Теория графов. М.: Мир, 1973.Работы автора по теме диссертации

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

34. Насыров А.З. Об обходе автоматами лабиринтов в п-мерном пространстве // Дискретная математика. 2000. - Т.12, вып. 4. - С. 121 - 137.

35. Насыров А.З. О бесконечной ловушке для автоматов со следом // Интеллектуальные системы. 2000. - Т.5, вып. 1-2.