Структурный анализ многоленточных автоматов

Под высотой диаграммы будем понимать максимальную высоту покрытий этой диаграммы. Очевидно

Утверждение 3.17. Число различных диаграмм дерева T конечно тогда и только тогда, когда высота диаграмм дерева T ограничена некоторым числом.

Будем говорить, что пара диаграмм D₁, D₂ удовлетворяет условию , если при применении к ним процедуры ₂ все используемые в p-границах вершины, где pP, являются входами макровершин.

Теорема 3.10. Если диаграммы D₁, D₂, удовлетворяют условию и алгоритм , на вход которого поданы эти диаграммы, не ломается, то высота диаграмм дерева T(D₁,D₂) ограничена числом, которое определяется по диаграммам D₁, D₂.

Доказательство основано на утверждениях 3.153.17, которые позволяют за счет структурных особенностей диаграмм, удовлетворяющих условию , получить оценку высоты диаграмм дерева T(D₁,D₂).

Если любая пара диаграмм D₁, D₂ множества M удовлетворяет условию , то такое множество обозначим M(), и будем говорить, что оно удовлетворяет условию .

Отметим, что, если будет справедлива выдвинутая нами гипотеза, то алгоритм будет алгоритмом разрешения эквивалентности для диаграмм множества M().

Обозначим M₁ класс однородных диаграмм.

Утверждение 3.21. M₁=M₁().

Следствие 3.5 теоремы 3.10. Алгоритм распознает -сечение однородных диаграмм.

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

Следствие 3.6 теоремы 3.9. Алгоритм распознает -сечение конечно-автоматных диаграмм.

В разделе 3.4 рассматривается применение трансформационного метода к конечным автоматам.

При применении трансформационного метода к эквивалентным конечным автоматам мы можем получить либо , либо -сечение и ничего другого. Доказано, что тип сечения зависит от порядка автоматов в паре (утверждение 3.21). Приводится достаточное условие, налагаемое на структуру графов, при которых сравниваемые эквивалентные автоматы непременно определяются -сечением (теорема 3.11).

В главе 4 приводятся результаты исследований по минимизации многоленточных автоматов.

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

Большинство моделей вычислений обладает некоторой структурой, и минимизация определяется как уменьшение объема этой структуры.

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

Задачу минимизации сформулируем следующим образом. Пусть M некоторое множество многоленточных автоматов:

по заданному автомату из М найти в классе его эквивалентности тупиковый автомат;

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

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

Глава 4 состоит из пяти разделов.

В разделе 4.1 описывается рассматриваемое нами множество M. Здесь же приводятся примеры автоматов из M, подтверждающие свойства, наличие которых обосновывает нетривиальность проблемы минимизации в M.

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

Рис. 4

Раздел 4.2 посвящен построению системы T э. п. автоматов, доказательству ее полноты в M, а также сводимости проблемы минимизации в M к одноименной проблеме в подмножестве множества M.

Система T использует аксиомы В1 и В2. В качестве аксиомы В1 рассматривается аксиома C3, описанная в разделе 2.1.

Аксиома B2 индуцирует преобразования, которые задаются парами фрагментов, тип которых изображен на рис. 5.

Двойные стрелки на рисунке обозначают непустое множество дуг, приходящих в указанное состояние. Совпадение меток, приписанных этим стрелкам (в качестве меток используются символы и с индексами), означает наличие взаимно однозначного соответствия между дугами помеченных множеств, сохраняющего метки дуг и состояния, из которых исходят эти дуги. Через F_p обозначены изоморфные подфрагменты фрагментов F₁ и F₂. Они очерчены на рис. 5 овалами.

Рис. 5

Достаточно описать лишь фрагмент F₁. Он имеет m, m 0, внутренних входов, все они являются q-состояниями, дуги из которых ведут в состояния a₁, a₂,…, a_m подфрагмента F_p и не принадлежат этому подфрагменту; приходящие в q-состояния непустые множества дуг обозначены ₁,…, _m. Фрагмент F₁ имеет n внешних выходов. Последние помечены символами b₁, b₂,…, b_n, а приходящие в них множества дуг обозначены ₁,…, _n.

Фрагменты F₁ и F₂ эквивалентны.

Терема 4.1. Система T полна в M.

Доказательство следует из возможности трансформирования преобразованиями В1 и В2 автомата в канонический и утверждения 4.4.

Приписыванием к аксиоме обозначим преобразование, индуцированное аксиомой, в котором фрагмент F₁ заменяется на фрагмент F₂ и , при замене фрагмента F₂ на F₁.

Автомат из M, к которому неприменимы преобразования В2, а к q-состояниям В1, назовем q-упорядоченным.

Справедлива

Лемма 4.1. Из эквивалентности состояний в q-упорядоченном автомате множества M следует их сильная эквивалентность.

Пусть K класс эквивалентных автоматов из M. Каноническим в K назовем автомат, полученный из q-упорядоченного применением всех возможных преобразований В1.

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

Следствие теоремы 4.1. В множестве M разрешима проблема эквивалентности.

Автоматом смешанного типа назовем автомат, содержащий как p-, так и q-состояния.

Обозначим подмножество множества M, состоящее из всех автоматов смешанного типа. Доказывается

Теорема 4.2. Проблема минимизации в M сводится к одноименной проблеме в .

Доказательство основано на том, что любой автомат множества M можно представить в виде цепочки автоматов, в которой подавтоматы состоящие только из q или только из p-состояний минимизируется независимо от подавтоматов смешанного типа.

Раздел 4.3 начинается с того, что произвольный класс эквивалентности K, принадлежащий множеству , разбивается на подклассы, называемые срезами класса K.

p-проекцией автомата D назовем автомат, полученный из D корректным устранением q-состояний: если преемником p-состояния является q-состояние, то преемник последнего объявляется преемником первого; это правило используется до тех пор, пока из D не устраняются все q-состояния.

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

Утверждение 4.7. Автоматы из главного среза класса K имеют минимальную p-проекцию среди всех срезов класса K.

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

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

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

Утверждение 4.8. Система T₀, индуцируемая аксиомами B0 и B2, полна в любом срезе класса K.

Действительно, преобразованиями по аксиомам B0 и B2 любой автомат из среза трансформируется в q-упорядоченный, а он единственный в срезе.

“Рабочим” преобразованием при осуществлении стратегии является, так называемое, -преобразование. Опишем его.

На вход -преобразования поступает фрагмент F₁ из описания аксиомы B2. Он представлен на рис. 5. Выполняется B2-преобразование, заменяющее фрагмент F₁ фрагментом F₂. Во фрагменте F₂ (см. рис. 6.) его внешние выходы b₁,…,b_n разбиваются на две группы: c₁,…,с_k и d₁,…,d_l, где k+l=n, k0, l0.

Рис. 6

В каждое состояние c₁,…,с_k приходит дуга из q-состояния, не входящего во фрагмент F₂, а всякое из состояний d₁,…,d_l не обладают этим свойством. На рис. 6 представлена данная ситуация. Фрагмент F₂ подвергается B0-преобразованиям, склеивающим q-состояния, и трансформируется во фрагмент, изображенный на рис. 7, который и объявляется результатом данного -преобразования.

Рис. 7

Раздел 4.4 посвящен реализации первого этапа. Основной в данном разделе является

Лемма 4.2. Любая конечная цепочка -преобразований трансформирует канонический в K автомат в тупиковый.

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

Теорема 4.3. Существует процедура построения всех минимальных автоматов в главном срезе класса K.

Предъявляется требуемая алгоритмизуемая процедура.

Раздел 4.5 посвящен реализации второго этапа. Устанавливается, что предположение стратегии действительно выполняются. Более того, предлагаемая процедура не только алгоритмизуема, но и является оптимальной по быстродействию.

Теорема 4.4. Каким бы ни был класс эквивалентности K из множества , существует процедура построения всех минимальных автоматов в K.

Но тогда из теоремы 4.4 и того факта, что рассматриваются лишь допустимые срезы, а также теоремы 4.2, о сводимости проблемы минимизации из M в , следует, что проблема минимизации в множестве M решена.

Основные результаты диссертационной работы

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

Основные полученные результаты состоят в следующем.

1. Для каждого из перечисленных ниже множеств построена полная в нем система эквивалентных преобразований:

для множества M_n,m, где n, m ? 2;

для подмножества автоматов с непересекающимися циклами, принадлежащих множеству M_2,2;

для подмножества однородных автоматов, принадлежащих множеству M_n,m, где n, m ? 2.

Здесь M_n,m это множество всех автоматов, использующих n бесконечных лент, которые заполняются символами алфавита, содержащего m символов; здесь n, m ? 2.

Построение систем э. п. и доказательство их полноты проводятся новыми подходами.

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

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

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

Использованием условия установлена разрешимость эквивалентности для автоматов с непересекающимися циклами, принадлежащих множеству M_n,m, n, m ? 2.

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

Установлено, что среди выделенных множеств находятся однородные автоматы, принадлежащие множеству M_n,m, n, m ? 2.

Установлено, что применение трансформационного метода к конечным автоматам проходит всегда в условиях завершаемости выполняемого им процесса.

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

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

Доказано, что искомым является множество двухленточных бинарных автоматов, работающих с лентами, одна из которых всегда заполнена одним и тем же символом из двух возможных:

показана нетривиальность этого множеств;

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

4. Очерчена область применимости трансформационного метода для моделей вычислений, отличных от многоленточных автоматов.

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

Считаю своим приятным долгом выразить глубокую признательность научному консультанту профессору Римме Ивановне Подловченко за постоянное внимание к работе.

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

эквивалентность многоленточный автомат трансформация

1. Хачатрян В.Е. О перестановочности логических графов // Кибернетика. 1976. № 3. С. 33-43.

2. Хачатрян В.Е. Однородные логические графы // Прикладная математика, изд-во Ереванского гос. университета. Ереван. 1981. С. 67-80.

3. Подловченко Р.И., Хачатрян В.Е., Чашин Ю.Г. Полная система эквивалентных преобразований для двухленточных автоматов с непересекающимися циклами // Программирование. 2000. № 5. С. 1-19.

4. Хачатрян В.Е., Чашин Ю.Г. Преобразование программ микропроцессорных систем управления // Известия высших учебных заведений. 2000. № 10. С. 135-139.

5. Подловченко Р.И., Хачатрян В.Е. Алгоритм распознавания эквивалентности многоленточных автоматов без пересекающихся циклов // Труды 5-межд. конф. Дискретные модели в теории управления систем. Ратмино-Москва. 2003. С. 67-70.

6. Хачатрян В.Е. Полная система эквивалентных преобразований для многоленточных автоматов // Программирование. 2003. № 1. С. 62-77.

7. Хачатрян В.Е., Рязанов Ю.Д. Структурный метод распознавания автоматной эквивалентности // Вестник БГТУ. 2003. № 6. ч. 3. С. 236-239.

8. Подловченко Р.И., Хачатрян В.Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд. сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 38-43.

9. Хачатрян В.Е., Чашин. Ю.Г. Использование преобразований для сравнения моделей на эквивалентность // Межд. научно-практ. конф. Информационные технологии в науке, образовании и производстве. Известия ОГТУ. 2004. № 2 (3). С. 53-57.

10. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности // Программирование. 2004. № 3. С. 3-20.

11. Хачатрян В.Е. О применении трансформацинного метода для распознавания эквивалентности многоленточных автоматов. // VI межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2004. С. 148-150.

12. Хачатрян В.Е. Трансформационные методы сравнения моделей на эквивалентность // Научные ведомости. Серия: информатика, прикладная математика, управление. Белгород. БелГУ. 2004. С. 40-51.

13. Хачатрян В.Е. О минимизации многоленточных автоматов. XIV межд. конф. Проблемы теоретической кибернетики. Пенза. 2005. С. 161-162.

14. Хачатрян В.Е., Щербинина Н.В. К вопросу о минимизации в моделях вычислений // Научные ведомости. Серия: информатика, прикладная математика, управление. Белгород. БелГУ. 2006. С. 34-51.

15. Хачатрян В.Е. Минимизация двухленточных автоматов // VII межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ.2006. С. 379-386.

16. Хачатрян В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН. 2006. том 411. № 3. С. 314-318.

17. Подловченко Р.И., Хачатрян В.Е. О построении минимальных по размеру двухленточных автоматов // IX межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2007. С. 348-351.

18. Хачатрян В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4. С. 52-55.

19. Хачатрян В.Е. Проблема эквивалентных преобразований для однородных многоленточных автоматов // Программирование. 2008. № 3. С. 77-80.

20. Подловченко Р.И., Хачатрян В.Е. Минимальность и тупиковость многоленточных автоматов // Дискретная математика. 2008. № 2. С. 92-120.

Размещено на Allbest.ru