Неотличимость конечных автоматов, взаимодействующих со средой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Саратовский Государственный университет им. Н.Г.Чериышевскогс

г ОД

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

КУРГАНСКИЙ Алексей Николаевич

НЕОТЛИЧИМОСТЬ КОНЕЧНЫХ АВТОМАТ!)В, ВЗАИМОДЕЙСТВУЮЩИХ СО СРЕДОЙ

01.01.09 - математическая кибернетика

Автореферат

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

Саратов - 1997

Работа выполнена в Институте прикладной математики и механик

ПАИ Украшши

Научные руководители - доктор технических наук,

профессор Д.В.Сперанский кандидат физико-математических наук, старший научный сотрудник И.С.Груиский

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

профессор, академик РАЕН В.А.Твердохлсбов кандидат физико-математических наук, доцепт В.В.Псчснкин

Ведущая организация - Институт проблем управления РАН

Защита состоится "_"_ 199_ года в _ часов на заседании специализированного Совета К 063.74.04 в Саратовском государственном университете им. Н.Г.Че.рнышеискогс (410071, Саратов, ул.Асграханская, 83).

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

Автореферат разослал "__"____199_года.

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

П.Ф. Недорезо]

Общая характеристика работы.

Актуальность работы. Конечные автоматы являются одним из главных объектов математической кибернетики. Они возникли как модели преобразователей дискретной информации, т.е. как модели взаимодействующие со средой — источником и получателем этой информации [5]. Автоматы в лабиринте [6], модель ЭВМ в виде взаимодействующих управляющего автомата и операционной среды [1], схема автоматов с выделенной, компонентой [4], автоматы, взаимодействующие через каналы связи [9] и, наконец, машины Тьюринга являются примерами такого взаимодействия.

Задача сравнения автоматов но поведению — одна из основных в теории автоматов. В случае, когда в качестве среды выступает экспериментатор, она в основном решена Муром [8]. Им рассматривалась задача сравнения автоматов простыми и кратными экспериментами. Более тонкое изучение неотличимости экспериментами проведено в [3]. Однако, в модели автомат-среда до сих пор изучалось в основном то, что может сделать автомат, и о проблеме неотличимости автоматов в среде известно не много. В работе [2] рассматривалась задача неотличимости автоматов по вход-выходным словам, порождаемым ими при взаимодействии с геометрическими средами без дыр: прямоугольниками фиксированной высоты, неограниченной высоты и их композициями. Доказано, что множества вход-выходных слов, порождаемых автоматами при взаимодействии с этими средами, является, в общем случае, контекстно-чувствительнными языками, т.е. задача неотличимости оказывается принципиально трудной и, возможно, алгоритмически неразрешимой. Для прямоугольников фиксированной высоты показано, что она разрешима.

В настоящей работе впервые введено отношение неотличи-

мости автоматов по вход-выходным словам, вырабатываемым ими при взаимодействии с одиой и той же средой. При этом в качестве среды выбран, возможно бесконечный и частичный, детерминированный автомат Мура. К такой модели среды сводятся многие ситуации и, в том числе, приведенные выше. Введенное отношение исследовалось в качественном и алгоритмическом аспектах. Качественный аспект рассмотрен по аналогии с подходами в [8,3]. Для исследования алгоритмической разрешимости проблемы неотличимости разработаны оригинальные методы.

Цель работы. Исследовать дескриптивные и алшритмиче-скис аспекты проблемы неотличимости автоматов, взаимодействующих с одной и той же средой: исследовать свойств» ограничений, вводимых средой; свойства ограниченного поведения автоматов; свойства класса автоматов, неотличимых относительно сред; исследовать алгоритмическую разрешимость проверки неотличимости автоматов.

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

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

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

Исследованы качественные свойства класса автоматов неотличимых относительно одной и той же среды, а именно:

- получены критерии его бесконечности, конечности и одно-элементности;

- дан критерий минимальности автомата в классе неотличи-

мости.

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

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

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

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

в [2];

- найдены неэффективные классы прямоугольников;

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

Заметим, что преобразование сред представляется мощным средством, позволяющим решать различные задачи теории автоматов.

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

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

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

Апробация. Результаты диссертации докладывались на школе-семинаре "Интеллектуальные системы" (Краскопидово, 1993 на II Украинской конференции по автоматическому управлению "Автоматика,-95" (Львов,1995), на XJ Международной конференции но проблемам теоретической кибернетики (УльяновскД996), па международной конференции "Интеллектуальные системы и компьютерные науки" (Москва,1996), на семинарах но теории управляющих систем ИПММ HAH Украины, в Саратовском и Донецком университетах.

Публикации. По теме диссертации автором опубликовало 4 работы (2 работы в соавторстве с И.С.Грунским). Список приводится в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы 31 наименования. Общий объем диссертации 102 страницы.

Обзор содержания диссертации.

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

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

В разделе 1.1 введены основные понятия. Под автоматом А ~ (Зл,Х,Г,6А,ЛА) понимается конечный детерминированный всюду определенный приведенный автомат Мили, где Я/,, X, У — множества, состояний, входных и выходных символов соответственно; 6д : х X —у <5д, : Бл х X У — функции переходов и выходов соответственно. Через обозначается множество всех вход-выходных слов, порожденных состоянием а автомата, а через А'ь — сужение этого множества на слова длины г.

Под средой понимается произвольный, возможно бесконечный (счетный) я частичный, детерминированный автомат Мура

где В,к — множество его состояния (вершин среды), V — входной алфавит, V — выходной алфавит (отметки вершин), В Лд(г, и) переменная и фиктивна, что позволяет применять запись Ае(г). Данное определение среды позволяет охватить широкий спектр сред (лента машины Тьюринга, геометрическая среда [6], операционная среда [1], часть схемы [4] и т.п.). Пусть Е„(Е) — множество всех таких пар (и, и) £ V х Г/, что для всех г € Яе с отметкой v значение ¿¿-(г, и) определено. Тогда Н(£') = и ЕЬ(Е).

Далее множества состояний автоматов всегда обозначаются символом Б с нижним индексом — именем автомата, а множество вершин сред — символом И с нижним индексом ■— именем среды.

Автомат и среда взаимодействуют между собой так, что выходной сигнал каждого из них совпадает с входным сигналом другого в каждый момент времени. Взаимодействие определяет автономный автомат Мили АЕ — (Зд х Re, z, Vr х Y, 6АЕ, Хае)-, где z — единственный входной сигнал, а

<W(-S »')>«) = А/.;(>')), <5 /Дг, АД*, Ajj(r)))),

Пары [s,r]> где s 6 S&, г G Д/?, называются конфигурациями автомата Л и среды Конфигурация [s,r] называется тупиком, если одно из значений 8ае(('ь г), z) или г), .г) но определено. Траекторией длииы г взаимодействия автомата А и среды 25, начинающейся конфигурацией [я, г], называется последовательность Тг •= [si, rj][s2, ?"2] • • •[в«>}*г]> Где l] = [5, г] и fi/t/iii-Sj, rf), z) — (s;+j, r\,-+j), 1 < j < i. Траектория Тг заканчивается конфигурацией js,-, ?-,•].

Автомат А и среда Е называются совместимыми, если автомат АЕ всюду определен. Критерий совместимости без труда следует прямо из определения и сформулировал в теореме 1.1.1. Для совместимых автомата и среды не ограничивая общности полагаем, что входной и выходной алфавиты среды совпадают с выходным и входным алфавитами автомата соответственно. Среду назовем правильной, если существует совместимый с ней автомат. Следствие 1.1.1 Среда Е является правильной в том и только том случае, если ее функция Ае всюду определена v БХ(Е) не пусто для каждой отметки вершин х.

Раздел 1.2 посвящен характеризации ограничений вводимых средой на множество вход-выходных слов, взаимодействующего ( ней автомата.

Зафиксируем правильную среду Е. Для совместимого с ней автомата А и состояния я £ Бд определим множество ЦазЕ всех вход-выходных слов конечной длины, порождаемых состоянием я при взаимодействии автомата и среды, т.е. ц^е = и г), г1)у

где объединение выполняется по всем г 6 Яд и натуральным г > 0. Обозначим через Ь(Е) множество всех слов (хъу\)... (.г,;, ¡л) в алфавите Е(£) гак их, что для некоторой вершины г среды Ау,;(г, у\ ... у,-) = X]... хи Множество Ь(Е) назовем ограничением, порожденным средой Е.

Теорема 1.2.1 Пусть автомат А совместим с правильной средой Е, 'тогда ¡1д0е — ^Лз П Ь(Е) для всех а 6 За-Следующая теорема дает критерий того, что произвольное множество слов Ь является ограничением, порожденным некоторой ере дой.

Теорема. 1.2.2 Пусть Ь - произвольное множество слов в алфавите X х У и 3 — Ь\. Тогда Ь является ограничением, порожденным некоторой средой, в том и только том случае, если одновременно выполняются свойства:

1. = ¡ь'

2. если 1и(х,у) £ Ь, где т £ Н+, (х,у) € Н, то ю(х1у>) С L для всех {х, у') £ Е;

У)\Ь Я: Ь для всех (ж, у) 6 В. В теореме приняты обозначения: Ь; - множество всех слов из Ь длины г, — множество всех начальных отрезков длины г

слов из ¿¿-и, (х,у)\Ь ~ множество всех слов т € 2* таких, что (х, у)ш £ Ь. В работе также найден критерий того, что Ь является ограничением, порожденным некоторой средой, выраженный через свойства множеств вход-выходных слов, порождаемых автоматами при этом ограничении (теорема 1.2.3).

В разделе 1.3 исследованы качественные свойства отношения

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

Пусть А и В совместимы с Е. Обозначим через ОъАЕ и Dae множества {i^e}seSA и {j'>Asb;}scSA соответственно. Состояния s € S л и t 6 Sb называются ¿-неотличимыми (неотличимыми) относительно Б, если [ilAsf; = f.ûBiE (jhisE — /î-iî/.£')• Автоматы A ж В — ¿-неотличимы (неотличимы) относительно Е, если D\K = ОгиЕ (Dae — Еве)- Отношение ¿-неотличимости (неотличимости) автоматов о тносительно Е обозначим через ffE (,%:). При исследовании отношения Ре в работе использована методика, разработанная в [3]. Она заключается в том, что исследуемое отношение между автоматами А ж В сводится к хорошо известному отношению (например, эквивалентности) между автоматами-характеризаторамн х(А) и х{В) производными от Л и В.

Поставим в соответствие автомату А и заданному г конечный, возможно, недетерминированный автомат-характеризатор xk(A) = (Оду, X, У, Длк, Алк), множество состояний которого равно 1У'АЕ. Функция выходов Але характеризатора определяется соотношением Aa{^1aseix) = Ал(.9, х), а. функция переходов Але — соотношением лл{^лзе1 х) = {^ме\(хi v)Vase < 11ла>;}> где у — Xa(s,x). Имеет место следующий критерий ¿-неотличимости.

Следствие 1.3.1 Автоматы А и В ¡-неотличимы относительно среды E в том и только том случае, если характе-ризаторы xk(^) п Хе(^) изоморфны.

Далее рассмотрена задача анализа: по A ni построить характери-затор Хе(А), и обратная ей задача синтеза автомата В G Ре{А)

по заданному г и характеризатору \lß(A). При этом доказано следующее утверждение.

Следствие 1.3.3 Если L(E) — рекурсивное множество, то для всех i существует алгоритм решения задач анализа и синтеза..

Следующее утверждение характеризует минимальные (но числу состояний) автоматы в классе ¿-неотличимости. Теорема 1.3.1 Автомат А является минимальным в классе ß);(A) о том и только том случае, если существует изоморфизм автомата А в свой характеризатар.

Далее оценивается мощность класса '¿-неотличимости. Ядром класса ß%(A) назовем наибольший (по числу состояний) автомат, изоморфно вложи Mi.1Й во L5CC автоматы класса. Теорема 1.3.2 Класс ßß(A) бесконечен в том и только том случае, если в характеризаторс Хе(^) впе я^Ра существует цикл.

Следствие 1.3.4 Равносильны утверждения:

1. класс ßß(A) состоит, из одного элемента;

2. характсризатор совпадает со своим ядром,, т.е. dein ермипир о а an;

3. этот класс имеет\ единственный минимальный по числу состояний автомат,.

Для отношения ßf;{A) неотличимости автоматов получены утверждения (теоремы 1.3.4-1.3.6, следствие 1.3.6) аналогичные следствию 1.3.1, теоремам 1.3.1, 1.3.2 и следствию 1.3.4. Исключение составляет задача анализа, которая, как показано ниже, для ßß в общем случае алгоритмически неразрешима.

Все формулировки утверждений о свойствах классов ¿-неотличимых автоматов практически дословно совпадают с формулировками аналогичных утверждений из [3] и являются обобщени-

ями последних. Такое обобщение представляется нетривиальным, поскольку охватывает поведение автоматов, взаимодействующих с тривиальными средами, т.е. такими, что всегда ¡iAsE — Ад, (они рассмотрены в [3]) и нетривиальными средами. Теоремы о мощности класса Дв(Д) для тривиальных сред вырождаются, т.к. в [3] показано, что для тривиальной среды класс всегда состоит

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

Теорема 1.3.7 Пусть Е произвольная правильная среда такая, что > 2 для всех отметок х вершин. Тогда среда Е тривиальна е том и только том случае, если для любого совместимого с Е автомата А класс Дё'(Д) одноэлементен.

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

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

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

Акцептором Л,о,л называется автомат А, в котором выделены два состояния: «о ^ начальное и s\ — заключительное. называется совместимым с Е, если А совместим с Е. Конфигурация [s,r], где s € 5л, т 6 Re, акцептора Л^л и среды Е называется начальной (заключительной), если s = sq (s — Si). Если существует траектория взаимодействия и Е (необязательно совместимых), которая начинается начальной и заканчивается заключительной (тупиковой) конфигурацией, то говорится, что Aao>ai

среде Е достигает заключительного состояния (достигает тупи-а). Следуюищй результат характеризует эффективность среды с разных точек зрения. Он показывает эквивалентность ряда задач, озникающих при взаимодействии автомата и среды, что позволят проводить сведение одной задачи к другой. Теорема 1.4.1 Пусть Е — произвольная правильная среда. Равносильны утверждения:

1. Среда Е эффективная;

2. Существует алгоритм, решающим задачу анализа (по i v, Е построить Xf:(A)J;

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

/¡, Существует алгоритм, который для любого акцептора проверяет достигнет ли акцептор тупика е Е или нет.

Из теоремы 1.4.1, в частности, вытекает простое утверждено.

Следствие 1.4.1 Для эффективности произвольной правильной среды Е достаточно, чтобы язык Ь{Е) был копте-'сгпно-свободным.

Сведение проблемы неотличимости к проблеме достюкимо-ти заключительного состояния является основой для оставшейся [асти работы.

Главы 2 и 3 посвящены построению эффективных сред.

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

В разделе 2.1 вводятся необходимые понятия и описываются [ростейшие преобразования, которые являются вспомогательными

для более сложных в последующих разделах.

Рассмотрим произвольный класс правильных сред

£ - {Ei}ieJ,

где I — множество индексов. Пусть среда Е равна объединению сред класса £ (под объединением сред понимается среда, полученная объединением дуг исходных сред с предварительным переобозначением вершин так, чтобы исходные среды не имели общих

вершин). Ясно, что тогда L(E) ~ U L(Ei). Класс сред £ naife/

зывается эффективным (правильным), если срода Е эффективна (правильна,). Далее класс сред и среда-, являющаяся объединением сред класса, не различаются.

Два класса сред £' и £" называются эквивалентными, если L{£') == L{£"), Из определений следует, что любая правильная среда, эквивалентная эффективной, также является эффективной (следствие 2.1.1) и любой правильный конечный класс эффективных сред является эффективным (следствие 2.1.2).

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

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

Для преобразования необходимо задать пять объектов Е, Т Д, V, I: 1) Е является исходной средой (классом сред) с входные алфавитом Y и выходным X = ..., жп}; 2) Т представля

т собой множество \<{<п классов сред ^{г) = {7/с(г)}Ае/(:)

входным алфавитом С} и выходным Р, где 1(Г) — множество ндексов, I < г < и, <ЗЛ У = 0; 3) / — это произвольное подмножество упорядоченпых наборов индексов из 7(1) х ... х 1(п); 4) ' = {Р(г)}1<1<п, где Р(г) — произвольное подмножество отметок з Р такое, что для любого р £ Г;(г) в каждой среде из !Р'(г) сущест-ует единственная вершина с отметкой р (эта вершина называется ем лее именем р); 5) Д = {%}т<!'^<п, где 8^ -- произвольная, сюду определенная функция из Р(1) X У в Р(.]), 1 < г,^ < п. Преобразование проводится отдельно для каждого табора 6 I. При этом преобразованная среда обозначается через 'в — (7£уй,<?иУ, Р, Л,/„). Полностью выполненное ирсобтюо--анме определяет класс сред ,/ = {Л]ее/-

Пусть е ~ (к\,... ,кп) (с целью упрощения дальнейших обо-иачетгай среда 7'\(г) обозначается через I < г < п). Тогда в реде Е каждая ее вершина тЕ £ Не заменяется множеством верши среды ге(г) /'ЦО £ ^(1), где г такое, что ж,; = Ае{ге), т.е. Ье = ип X Гц, где Ау,;()>;) = ж».

Далее по следующим формулам на новом множество вер-тин определяются функции выходов А/е и переходов Ь,),,. Пусть г,те) € Р.Гг и вершина г/,; имеет отметку тогда 1) ф',гЕ) = Аи 2) 8^((г,гЕ),у) равно ■)(»•, у), г^), если € <5, и равно (<^-(г,у),<5в(г/,;,у)), если у € У, где такое, что ^ является отметкой вершины 8е(гЕ->у)- Если правая часть в но-ледней формуле не определена, то не определена и левая часть.

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

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

В разделе 2.4 рассмотрено двумерное, преобразование. Найдено достаточное условие (теорема 2.4,1), при котором преобразование переводит эффективную среду и эффективную. Результат используется в разделе 3.3, где рассмотрен частный случай данного преобразования, когда указанное условие проверяется конструк тивно.

Глава. 3 посвящена построению эффективных геометрических

сред.

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

Конечную правильную среду Е назовем лентой, если все с< вершины можно расположить в последовательность ггг2... г к та кую, что все инцидентные в графе среды вершины в последователь ности стоят рядом, где к — число вершин данной среды. Зафик

;ируем одну из таких последовательностей гх.,. г,... гвершин гепты Е. Ленту Е назовем канонической, если 1) ее входной алфавит содержит не более трех символов, на,пример, {—1.,+1,0}, и если значения 8е(?{, — 1), ¿д(г!-, +1), ¿¿'(г;, 0) определены, то они эавны г;_ 1, г1+1, гг- соответственно, 1 < г < А;. Формулой канонирской ленты /? назовем слово А/,;(?'])Ад(г2) ... А;,;(г/;), Формулой &(£) правильной) класса канонических лепт £ пазовом множество (юрмул всех лент Е £ £. Путем сведения акцепторов, взаимодействующих с к машинам Тьюринга без записывающей головки, юкалап критерий эффективности лент.

Следствие 3,1.3 Произвольный класс каиоппчссгсих лепт £ уффектиосп в том % только том случае, если, существует глгоритм, который для любого регулярного языка М проверяет пустоту множества МпФ(£).

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

В разделе 3.2 применен метод одномерного преобразования тент при исследовании геометрических сред. Введем необходимые тонятия.

Пуст ь Ет — т-мсрпос целочисленное пространство. Обозначим через е™ т-мериый вектор, у которого г-ая компонента равна I, все остальные равны 0,1 < I < тп. Тогда т-мерной геометрической средой называется среда О с множеством верши п На Я входным алфавитом <3 = {—+ер}1<г<т и алфавитом отметок вершин таких, что отметка каждой вершины г € Яа взаимнооднозначно указывает на то, какие из вершин г +• А принадлежат Па, где (I € ф. При этом, если г + ^ £ Яа, то ¿) — г + д,.

Размер произвольного класса 0 т-мерных геометрических

сред называется ограниченным в ¿-ой координате числом А,, ее ли для всех в € 0 и ..., 4..., 4), (г;',..., ..., 4) € имеем \г[ - г<'| < к. Пусть Т{Ь) = {0,1,...,/г.}, к е 2, к > О, Т(к],..., кт) = Т(Ь,\) х ... х Т(Лт). Тогда среда с множеством вершин Т(кх,... ,кт) называется т-мерным прямоугольником с размерами /¿|,..., кт но координатам 1,..., т соответственно. Следствие 3.2.1 Класс всем: т-мерных геометрических сред, ограниченных по произвольным т — 1 координатам, являете,}, эффективным.

Следствие 3.2.2 Класс всех гп-мерпых прямоуяолыткоа с фиксированными размерами по произвольным т —1 координатам является эффективным.

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

Раздел 3.3 является продолжением раздела 2,4. Благодаря удобному представлению классов лент в виде формул, появилась возможность описать частный случай двумерного преобразования сред (необязательно лент), при котором эффективность результирующей среды следует из эффект икности исходной — как и п случае одномерного преобразования. Цель данного раздела построить эффективный класс ¡тометричсских сред, доказательство эффективности которого средствами одномерной) преобразования лет невозможно.

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

Теорема 3.3.1 Если среда J получена двумерным преобра зовапием эффективпой среды Е по заданным Т, V, Л, I, пръ котором Т представляет собой мнооюеетво классов лент

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

С помощью указанного преобразования в разделе доказана эффективность класса геометрических сред 'Я, каждая среда Нц хоторого задается парой целых чисел к, I, где к > Ли является нечетным числом, I > 2. При этом точка является верши-

:юй среды Ду, если 1) 1 < < к, 1 < < I, 2) - нечетное гасло, либо, если 2] — четное, то ^ = 1 или ¿'а — I- Таким образом найден эффективный класс геометрических сред, содержащий :реды со сколь угодно большими размерами но обеим координатам.

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

Следствие 3.4.1 Геометрическая среда с множеством, вершин 7?' является неэффективной.

Следствие 3.4.2 Произвольный класс Ч-мерных прямоугольников такой, что для любого сколь угодно большого числа з нем найдется прямоугольник с размерами превышающими это число, является неффехтивпым. Далее доказано, что всякий класс геометрических сред, содержащий неэффективный подкласс прямоугольников, является неэффективным. Из этого утверждения следуют критерии эффективности некоторых сред, например:

Следствие 3.4.6 Класс всевозможных т-мерпых геометрических сред с ограниченными размерами по координатам из заданного списка эффективен в том и только том случае,

если список содержит не менее чем m — 1 координат.

Автор выражает глубокую благодарность Игорю Сергеевич} Груискому и Дмитрию Васильевичу Сперанскому за постановку задачи и многолетнюю помощь и поддержку.

Список цитированной литературы

1. Глушков В.М., Цейтлин Г.Е., Ющенко E.J1. Алгебра, языки, про граммирование. - Киев: Наук.думка, 1989. 37бе.

2. Г ру иска я В. И. О некоторых свойствах траекторий автомата! в лабиринтах: Диссертация канд. физ.-мат. наук: 01.01.09/ АН России. МГУ. - Москва, 1995. - 190л.

3. Грунский U.C., Козловский В.А., Пономаремко Г.Г. Представление конечных автоматов фрагментами поведения. - Киев: На ук.думка, 1990. - 232с.

4. Кудрявцев В.Б. Функциональные системы. М.: Изд-во МГУ 1982. 158с.

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

6. Кудрявцев В.Б., Ущумлич Ш., Килибарда Г. О поведении авто матов в лабиринтах // Дискрет, математика. -1992. - 4, вып.З

- С.3-28.

7. Минский М. Вычисления и автоматы. - М.: Мир, 1971. - 366с.

8. Мур Э.Ф. Умозрительные эксперименты с последователыюст ными машинами // Автоматы. - М.: Изд-во иностр. лит., 195G

- С.179-210.

9. Gouda M.E., Manning E.G., Yu Y.T. On the progress of communication between two finite state machines // Information and Control. - J 984. 63, Ai 3. - P.200-216.

Публикации автора по теме диссертации

1. Грунский И.С., Курганский А.Н. Неотличимость конечных автоматов, взаимодействугощих со средой // Докл. АН Украины. 1993. - ныи.П. С.31-33.

2. Грунский ИХ., Курганский Â.H. Неотличимость коисшых автоматов с ограниченным поведением // Кибернетика, и системный анализ. - 1996. -JV5. С.58 72.

3. Курганский А.Н. Об эквивалентности конечных автоматов, взаимодействующих с лабиринтами // Лвтоматяка-9П: Тезисы докл. II Украинском конференции по автоматическому управлению. - Львов, 1996. - Т 1. С. 158.

4. Курганский A.N. Эквивалентность автоматов, взаимодействующих со средой // Проблемы теор. кибернетики: Тезисы докл. XI Международной конференции. - Ульяновск, 1996. -- СЛ15.