Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Структурный анализ многоленточных автоматов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Предлагаемая работа посвящена решению фундаментальных проблем классической модели вычислений — многоленточных автоматов, введенной М. Рабином и Д. Скоттом в 1959 году в их классической статье. Эта модель является естественным обобщением конечных детерминированных автоматов, состоящим в переходе от одной ленты, несущей информацию для работы автомата, к нескольким лентам. Последнее означает, что… Читать ещё >

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

Содержание

  • 1. Основные понятия, постановка рассматриваемых задач и средства их решения
    • 1. 1. Определение многоленточного автомата
    • 1. 2. Рассматриваемые проблемы в теории многоленточных автоматов
    • 1. 3. Проблема эквивалентных преобразований
    • 1. 4. Проблема эквивалентности и включения
    • 1. 5. Проблема минимизации и поиска всех минимальных форм
    • 1. 6. Фрагментные преобразования. Общий подход к решению проблем
  • 2. Частичная разрешимость проблемы эквивалентности в множестве всех детерминированных бинарных многоленточных автоматов и в двух его подмножествах (построение полных систем э. п.)
    • 2. 1. Полная система фрагментных преобразований для многоленточных автоматов
    • 2. 2. Полная система для автоматов с непересекающимися циклами
    • 2. 3. Полная система для однородных автоматов
  • 3. Трансформационный метод анализа структуры многоленточных автоматов
    • 3. 1. Метод трансформационного распознавания эквивалентности в моделях вычислений
    • 3. 2. Применение трансформационного метода для случая автоматов с непересекающимися циклами
    • 3. 3. Достаточное условие применимости трансформационного метода и его использование
    • 3. 4. Классификация сечений для конечных автоматов
    • 3. 5. Использование трансформационного метода для случая с неразрешимой проблемой включения
  • 4. Обобщенная проблема минимизации и ее решение в одном классе двухленточных автоматов
    • 4. 1. Множество М детерминированных бинарных двухленточных автоматов и некоторые их свойства
    • 4. 2. Система Т эквивалентных преобразований автоматов и сведение обобщенной проблемы минимизации из М в М
    • 4. 3. Срезы класса эквивалентности и стратегия поиска минимальных автоматов в классе эквивалентности
    • 4. 4. Главный срез и минимальные в нем автоматы
    • 4. 5. Допустимые срезы класса эквивалентности и построение минимальных автоматов в них

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

Классическими моделями вычислений являются алгебраические выражения, формулы логики, конечные автоматы, абстрактные вычислительные машины, схемы программ и другие [2,4,5,9,11,13,23,72,84,102,110]. Исследование моделей вычислений позволяет, с одной стороны, заняться только изучением тех конкретных свойств, которые заложены в данную модель вычислений, абстрагируясь от всех остальных, что позволяет обычно добиться положительного результата ввиду упрощения исходной задачи. С другой стороны, полученные результаты обычно переносимы на более сложные реальные объекты. Это достигается путем наложения на последние дополнительных ограничений, нацеленных на возможность использования исследованной модели вычислений.

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

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

Предлагаемая работа посвящена решению фундаментальных проблем классической модели вычислений — многоленточных автоматов, введенной М. Рабином и Д. Скоттом в 1959 году в их классической статье [110]. Эта модель является естественным обобщением конечных детерминированных автоматов, состоящим в переходе от одной ленты, несущей информацию для работы автомата, к нескольким лентам. Последнее означает, что это модель многозадачного процесса вычислений, поскольку работа на одной ленте может восприниматься как работа, выполненная одной задачей обладающей возможностью коммутировать с остальными. При этом в каждой цепочке задач, начинающихся во входе и заканчивающихся в выходе число выполнений каждой задачи данной разновидности, должно сохраняться. Исследуемая модель не является универсальной моделью вычислений. В [110] установлено принципиальное отличие функциональных свойств многоленточных автоматов от одно ленточных, а именно:

— неразрешимость проблемы включения для многоленточных автоматов;

Установлено также [110], что в отличие от обыкновенного (одноленточного) конечного автомата, недетерминированные многоленточные автоматы более мощные, чем детерминированные. Это утверждение справедливо и для случая двухленточного автомата.

Для недетерминированных многоленточных автоматов (даже для двухленточных автоматов, которые обычно называются конечными преобразователями) проблема эквивалентности является стандартным примером неразрешимой проблемы [67]. Этот результат неразрешимости был впервые доказан Т. Гриффитсом в 1968 г. [77].

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

Не останавливаясь на всех полученных результатах, отметим те, что являются в известном смысле заключительными. М. Бердом в 1973 [65] показана разрешимость проблемы эквивалентности для двухленточных автоматов. Альтернативное решение для случая двухленточного автомата было дано в [118]. Многочисленные попытки [103,98,71,54,8,7] решить главную проблему привели только к очень скромному успеху, и лишь Т.

Харью и Дж. Кархумяки в 1991 [87] доказали разрешимость в случае любого количества лент.

Особо отметим, что результаты, полученные в [65,118,87], связаны с рассмотрением моделей более широкого толкования, чем многоленточные автоматы. Так М. Бердом исследовались недетерминированные диаграммы, а Т. Харью и Дж. Кархумяки воспользовались Теоремой Равенства Айленберга (Eilenbergs Equality Theorem) [72] для решения множественной эквивалентности для недетерминированных многоленточных автоматов, к которым сводится эквивалентность многоленточных автоматов.

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

— установление частичной разрешимости автоматов путем построения полной системы их э. п.;

— исследования, связанные с использованием достаточных условий эквивалентности;

— построение минимальных по размеру автоматов в классе их эквивалентности.

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

Достиэ/сение цели связывается с решением следующих задач:

• расширение понятия допустимого фрагментного преобразования;

• построение полных систем эквивалентных преобразований, как для всего класса многоленточных автоматов, так и для его подклассов;

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

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

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

При разработке фрагментных преобразований используется опыт предшествующих исследований автора [49 — 53].

Основной результат. Разработан и обоснован новый аппарат (структурный анализ) решения фундаментальных проблем для модели вычислений — многоленточные автоматы, основанный на использовании систем фрагментных преобразований:

В главе 1 дается классическое [9], а также используемое в работе [102] определение многоленточного автомата. Формулируется исследуемая проблематика теории многоленточных автоматов и стратегия их решения [38, 34, 43, 14]. Предлагается решение проблем осуществлять для бинарных многоленточных автоматов с последующим переносом полученных результатов на произвольные многоленточные автоматы [102]. Описывается применяемый при исследованиях аппарат [14,15,41,42,47]. Определяются понятия фрагмента, допустимого преобразования, контекстно-зависимого преобразования [38], исчисления фрагментных преобразований и полных систем [15,16].

Формулируются основные проблемы, решаемые в главах 2 — 4 и общие подходы к их решению.

В главе 2 для каждого п, ш, (п, ш > 2) приводится система э. п., являющаяся полной в множестве М", т [38]. Здесь через Мп>т обозначено множество п-ленточных автоматов над ш-символьным алфавитом. Разработка э. п. основана на структурно-семантическом анализе рассматриваемого отношения эквивалентности и не предполагает наличия алгоритма разрешения эквивалентности, а значит и его использования.

При решении конкретных практических задач требуется рассмотрение лишь определенных подклассов модели вычислений. В связи с этим, приводятся полные системы э. п. для подклассов автоматов с непересекающимися циклами [30] и однородных [54].

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

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

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

Глава 3 посвящена рассмотрению задачи построения разрешающего алгоритма в моделях вычислений, объекты которых представлены конечными ориентированными графами с разметкой. Предлагаемый подход отличается от изложенного в [87] и назван трансформационным [34], поскольку для распознавания эквивалентности объектов применяет эквивалентные их преобразования.

Отметим, что близким по идейному замыслу, но выводящим из класса детерминированных объектов в класс недетерминированных, является алгоритм разрешения эквивалентности двухленточных автоматов, предложенный Р. Бердом в [65].

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

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

Проводится апробация метода [35] на конечных детерминированных многоленточных автоматах с непересекающимися циклами.

Приводится алгоритм, применяемый к паре многоленточных автоматов, и формулируется гипотеза о достаточном признаке, при наличии которого в классе многоленточных автоматов приведенный алгоритм является алгоритмом разрешения эквивалентности [41].

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

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

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

Установлено следующее принципиальное отличие двухленточных автоматов (следовательно, и многоленточных) от обычных конечных. Существуют классы эквивалентных детерминированных бинарных автоматов, содержащие несколько минимальных по размеру автоматов [47]. Это нарушает известную картину для конечных автоматов, где минимальным в классе эквивалентных автоматов является всегда единственный автоматим является тупиковый автомат, т. е. такой, который не имеет двух различных эквивалентных состояний. В случае же двухленточных автоматов минимальные тоже являются тупиковыми, но, как мы показали, тупиковых автоматов может быть и бесконечное число в одном и том же классе эквивалентных автоматов [47].

Эти результаты получены для детерминированных бинарных двухленточных автоматов, структура которых незначительно отличается от структуры конечных, т. е. одноленточных автоматов. Рассматриваемое множество автоматов обозначено М.

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

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

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

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

Работа поддерживалась следующими грантами: грант РФФИ 03−01−132а, грант РФФИ 06−01−106, внутренними грантами Белгородского государственного университета ВКГ 031−06 и ВКГ 176−07. и.

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

Заключение

.

Перечислим основные научные результаты, представленные в докторской диссертации:

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

2. Расширено понятие фрагментного преобразования, что позволило:

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

• построена полная система эквивалентных преобразований с доказательством разрешимости проблемы эквивалентности для однородных автоматов;

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

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

•трансформационным методом доказана разрешимость проблемы эквивалентности для автоматов с непересекающимися циклами;

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

•описаны достаточные условия для проведения классификации по характеристикам сечений как для классов многоленточных, так и конечных автоматов;

•доказано, что предложенный метод работает в случае неразрешимости проблемы включения.

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

•описан алгоритм минимизации для автоматов этого класса.

Показать весь текст

Список литературы

  1. В.Б., Ложкин С. А. Элементы теории графов, схем и автоматов (учебное пособие для студентов) — М.: Издательский отдел ф-та ВМиК МГУ, 2000 г. 58.с.
  2. В. Введение в теорию конечных автоматов, под ред. Ю.И. Журавлева-М.: Радио и связь, 1987. -З92.с.
  3. А.П. Об операторных схемах Янова, сб., Проблемы кибернетики, вып.20, М., Наука, 1967.
  4. А.П. Смешанные вычисления // В мире науки. 1984. № 6. с. 2842
  5. Ю.И., Флёров Ю. А. Дискретный анализ. 4.1: Учебное пособие. М.: Изд-во МФТИ, 1999.
  6. . Ю.И., Гуревич И. Б. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика, 1974, № З.с. 1620.
  7. A.A. О проблеме эквивалентности многоленточных автоматов, один из которых произвольный. ВЦ ЛГУ
  8. Е.Б. Об одном классе многоленточных автоматов с разрешимой проблемой эквивалентности // Программирование, 1983, № 3, с. 3−16
  9. В.Е., Сабельфельд В. К. Теория схем программ. Москва: Наука. 1991. с. 248
  10. A.A. Практические методы распознавания эквивалентности дискретных преобразователей и схем программ// Кибернетика, 1973, № 4, с. 15−26.
  11. A.A. Функциональная эквивалентность дискретных преобразователей//Кибернетика, № 2, 1969, с. 15−17- № 2,1970, с. 14−29- № 1, 1972, с. 1−5.
  12. О. Б. Об одном подходе к синтезу управляющих систем -принципе локального кодирования. Проблемы кибернетики, вып. 14, М., Наука, 1965, с. 31−110.
  13. A.A. О логических схемах программ // Проблемы кибернетики, вып. 1, М.: Физматгиз, 1958, с. 46−74.
  14. Р.И., Хачатрян В. Е. О построении минимальных по размеру двухленточных автоматов // IX межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2007.С. 348−351.
  15. Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, № 6, с. 3−14
  16. Р.И., Айрапетян М. Г. О построении полных систем эквивалентных преобразований схем программ // Программирование, 1996. № 1. с. 3−29.
  17. Р.И., Полная система подобных преобразований R-схем, сб., Проблемы кибернетики, вып.27, М., Наука, 1973.
  18. Р.И. Алгоритм канонизации пар схем программ с перестановочными операторами // Программирование, 1997, № 6,с.3−16.
  19. Р.И. О построении полных систем эквивалентных преобразований схем программ // Труды XII Международн. конф. «Дискретные модели в теории управляющих систем», М., Диалог-МГУ, 1997, с. 46−47.
  20. Р.И. Система преобразований, полная в классе схем программ с перестановочными операторами // Программирование, 1998, № 2, с. 58−67.
  21. Р.И. Система преобразований, полная в классе схем программ с перестановочными операторами // Программирование. 1998. № 2. С. 58−67.
  22. Р.И. От схем Янова к теории схем программ // Математические вопросы кибернетики, М., Физматлит, 1998, вып. 7, с.281−302.
  23. Р.И. Об одном семействе полных систем эквивалентных преобразований схем программ // Тезисы докл. XII Международной конф. «Проблемы теоретической кибернетики», (Нижний Новгород, 1722 мая 1999), М., изд. мех.-мат. ф-таМГУ, 1999, ч. 2, с. 187.
  24. Р.И. Об одном массовом решении проблемы эквивалентных преобразований схем программ. I //Программирование, 2000, № 1, с. 64−77.
  25. Р.И. Об одном массовом решении проблемы эквивалентных преобразований схем программ. II //Программирование, 2000, № 2, с. 3−11.
  26. Р.И. К вопросу об эквивалентных преобразованиях алгоритмов и программ // Математические вопросы кибернетики, М., Физматлит, 2000, вып. 9, с. 25−36.
  27. Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики, М., Физматлит, 2007
  28. Р.И. Иерархия моделей программ //Программирование, 1981, № 2, с.3−13.
  29. Р. И., Хачатрян В. Е., Чашин Ю. Г. Полная система эквивалентных преобразований для двухленточных автоматов с непересекающимися циклами // Программирование. 2000. № 5. С.1−19.
  30. Р.И. Эквивалентные преобразования схем программ для «запутывания» самих программ // Программирование, 2002, № 2, с. 66−80.
  31. Р.И. Проблема эквивалентных преобразований в модели программ с перестановочными и монотонными операторами // Программирование, 2002, № 6, с. 1−17.
  32. Р.И., Хачатрян В. Е. Алгоритм распознавания эквивалентности многоленточных автоматов без пересекающихся циклов // Труды 5-межд. конф. Дискретные модели в теории управления систем. Ратмино-Москва. 2003. С. 67−70.
  33. Р.И., Хачатрян В. Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд.сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 38−43.
  34. Р.И., Хачатрян В. Е. Об одном подходе к разрешению проблемы эквивалентности // Программирование. 2004. № 3. С. 1−17.
  35. Подловченко Р. И, Хачатрян В. Е. Минимальность и тупиковость многоленточных автоматов // Дискретная математика. 2008. № 2. с. 130.
  36. В. К. О преобразовании унарных линейных рекурсивных схем // Кибернетика, 1975, № 5, с. 56−66
  37. В.Е. Полная система эквивалентных преобразований для многоленточных автоматов //Программирование. 2003. № 1. С.62−77.
  38. В.Е., Рязанов Ю. Д. Структурный метод распознавания автоматной эквивалентности // Вестник БГТУ. 2003. № 6. ч.З. С. 236 239.
  39. В.Е., Чашин. Ю. Г. Использование преобразований для сравнения моделей на эквивалентность // Межд. научно-практ.конф. Информационные технологии в науке, образовании и производстве. Известия ОГТУ. 2004. № 2(3). С. 53−57.
  40. В.Е. О применении трансформацинного метода для распознавания эквивалентности многоленточных автоматов. // VIмежд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2004. С. 148−150.
  41. В.Е. Трансформационные методы сравнения моделей на эквивалентность // Научные ведомости. Серия: информатика, прикладная математика, управление. Белгород. БелГУ. 2004. С. 40−51
  42. В.Е. О минимизации многоленточных автоматов. XIV межд. конф. Проблемы теоретической кибернетики. Пенза. 2005. С. 161−162.
  43. В.Е., Щербинина Н. В., К вопросу о минимизации в моделях вычислений. // Научные ведомости. БелГУ. Сер. Информатика и прикладная математика, № 2(31), вып. З,. 2006. С. 42−59.
  44. В.Е. Минимизация двухленточных автоматов // Труды VII межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ.2006. С. 379−386.
  45. В. Е. Чашин Ю. Г. Преобразование программ микропроцессорных систем управления// Известия высших учебных заведений. 2000. № 10. С. 135−139.
  46. В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН. 2006. том 411. № 3. С.314−318.
  47. В.Е. Системы преобразований, сохраняющих различные отношения эквивалентности схем программ. Диссертация на с.у.с.канд. физ-мат наук. Ереван 1979 г.
  48. В.Е. О перестановочности логических графов //Кибернетика. 1976. № 3. С. 33−43.
  49. В.Е. Об отношениях перестановочности в схемах Янова. //Программирование. 1976. № 4. С. 3−12.
  50. В.Е. Логико-термальная эквивалентность в классе схем над сильно-невырожденным базисом //Программирование. 1977.№ З.С.20−27.
  51. В.Е. Полные системы D-эквивалентных преобразований схем Янова//Программирование. 1978. № 3. С. 16−27.
  52. В.Е. Преобразования сохраняющие D-эквивалентность схем Янова (общий случай) // Программирование. 1979. № 1. С. 3−10.
  53. В.Е. Однородные логические графы// Прикладная математика, изд-во Ереванского гос. университета. Ереван. 1981. С. 6780.
  54. В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4.с.1−6.
  55. В.Е. Проблема эквивалентных преобразований для однородных многоленточных автоматов //Программирование. 2008. № 3. с. 1−6.
  56. C.B. «Эквивалентные преобразования управляющих систем», Методическая разработка по курсу «Элементы кибернетики», МГУ, ВМК, 1986, с. 1−40.
  57. С. В. Элементы математической кибернетики-. М.: Высшая школа, 2007, 191 с.
  58. Ю.И. Проблемы кибернетики, вып. I, М: Физматгиз, 1958, с.75−127.
  59. Ю.И. Несколько теорем о свертках, АН СССР, ИПМ им. М. В. Келдыша, Москва. 1978. С. 1−73.
  60. Ю.И. О локальных преобразованиях схем алгоритмов // Проблемы кибернетики, вып. 20, -М.: Наука, 1968, с. 201−216
  61. Aho, А.V., Sethi, R., and Ullman, J.D. Compilers: Principles, Techniques, and Tools. Addison-Wesley 1986
  62. Angluin, D. Inference of reversible languages. Journal of the ACM 29, (1982), 741−765.
  63. Arnold, A., Dicky, A., and Ni vat, M. A note about minimal nondeterministicautomata. Bull. European Assoc. Theoret. Comput. Sci. 47 (1992), 166−169.
  64. Bird R. The equivalence problem for deterministic two-tape automata // J. of Computer and System Science, 1973, 7, № 4. p. 218−236.
  65. Berstel J. Trasductions and Context-Free Languages (B.G.Teubner, Stuttgart, 1977).
  66. Berstel J. and Reutenauer C. Rational series and Their Languages (Springer, erlin, 1988).
  67. Champarnaud, J.-M., and Coulon, F. NFA reduction algorithms by means of regular inequalities. In Proceedings of DLT 2003, Lecture Notes in Computer Science 2710, Springer, 2003, 194−205.
  68. Cohn P.M. Free Rings and their Relations, 2nd edn. (Academic Press. New York, 1985)
  69. K. 11 and Karhumaki J. HDTOL matching of computations of multitape automata, Acta Inform. 27 (1989) 179−191.
  70. Eilenberg S. Automata, Lnguages, and Macines, Vol. A (Academic Press, New York, 1974).
  71. Elgot C.C., and Mezei, J.E. On relations defined by generalized finite automata. IBM J. Res. Develop. 9, (1965), 47−68.
  72. Fisher P. Multi-tape and infinite-state automata. Communications of the ACM, 1965,8:799−805.
  73. Fischer P.C., and Rosenberg, A.L. Multitape one-way nonwriting automata. J. Comput. System Sci. 2, (1968), 88−101.
  74. Fuchs L. Partially Ordered Algebraic Systems (Pergamon Press, Oxford, 1963).
  75. Griffiths T.V. The insolvability of the equivalence problem for X-free nondeterministic generalized machines. J. ACM, 15,3 (1968), 409−413.
  76. Grigorieff S. Modelization of deterministic rational relations. Theoretical Computer Science, 281, (2002), 423D453.
  77. Glaister, I., and Shallit, J. A lower bound technique for the size of nondeterministic finite automata. Inform. Proc. Letters 59, (1996), 75−77.
  78. Grahne, G., Hakli, R., Nyk’anen, M., Tamm, H., and Ukkonen, E.
  79. Design and implementation of a string database query language. Information Systems 28, (2003), 311−337.
  80. Grahne, G., Nyk’anen, M., and Ukkonen, E. Reasoning about strings in databases. J. Comput. System Sci. 59, (1999), 116−162.
  81. Grigorieff S. Modelization of deterministic rational relations. Theoretical Computer Science, 281, (2002), 423−453.
  82. Harju T. and Karkumaki J. Decidability of the multiplicity eguivalence problem of multitape finite automata, in: Proc. 22nd STOC (1990) 477−481.
  83. Hopcroft J. E., Motwani, R. and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001
  84. Hakli R., Nyk’anen, M., and Tamm, H. A declarative programming system for manipulating strings. In Sixth Fenno-Ugric Symposium on Software Technology, Sagadi, Estonia, 1999, 29−40.
  85. Harju T., Karhumaki J. The equivalence of multitape finite automata // Theoret. Computer Sci., 1991, 78, p. 347−355.
  86. Hopcroft J. An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-190, Stanford University, 1971.
  87. Hopcroft J.E., Motwani, R. and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.
  88. Hopcroft J.E., and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 1979.
  89. Ilie L., and Yu S. Algorithms for computing small NFAs. In Proceedingsof MFCS 2002, Lecture Notes in Computer Science 2420, Springer, 2002, 328−340.
  90. Ilie L., and Yu S. Reducing NFAs by invariant equivalences. Theoretical Computer Science, 306, 2003, 373−390.
  91. Ilie L., Navarro G., and Yu, S. On NFA reductions. In Theory is forever, Lecture Notes in Computer Science 3113, Springer, 2004, 112−124.
  92. Jacobson N. Lectures in Abstract Algebra, Vol. 11 (Van Nostrand, New York, 1953).
  93. Jiang Т., and Ravikumar B. Minimal NFA problems are hard. SIAM J. Comput. 22, 6 (1993), 1117−1141.
  94. Karhumaki J. On Recent Trends in Formal Language Theory, Lecture Notes in Computer Science 267 (Springer, Berlin, 1983) 136−162.
  95. Kinber E. The inclusion problem for some classes of deterministic multitape automata, Theoret.Comput.Sci. 26 (1983) 1−24.
  96. Kameda T. and Weiner P. On the state minimization of nondeterministic automata. IEEE Trans. Comput. C-19, 7 (1970), 617−627.
  97. Karhurrfaki J. Applications of finite automata. In Proceedings of FCS 2002, Lecture Notes in Computer Science 2420, Springer, 2002, 40−58.
  98. Khachatryan V.E. Complete system of equivalent transformations for multitape automata. Programming and Computer Software 29, 1, (2003), 43−54
  99. Luckham D.C. Park D.M., Paterson M.S. On formalized computer programs// JCSS, 1970. 4, № 3, p. 220−249. (Русский перевод:
  100. Кибернетический сборник. Новая серия, М: Мир, 1975. № 12, с. 78−114).
  101. Lewis Н.Р. A new desidable problem, with application. Proc. 18 Ann. Symp. On Foundation of Сотр. Sci. 1979. P. 62−73.
  102. Matz O. and Potthoff, A. Computing small nondeterministic finite automata. In Proceedings of the Workshop on Tools and Algorithms
  103. Muder D.J. Minimal trellises for block codes. IEEE Trans. Inform.
  104. Neumann B.N. On orderd division rings, Trans. Amer. Math. Soc. 66 (1949) 202−252.
  105. Passman D.S. The Algebraic Structure of Group Rings (Wiley, New York, 1977).
  106. Pin J.-E. On reversible automata. In Proceedings of the first LATIN conference, Lecture Notes in Computer Science 583, Springer, 1992, 401−416.
  107. Post E. A variant of recursively unsolvable problem, Bull. Amer. Math. Soc., 52(1946), p. 264 268.
  108. Rabin M.O., Scott D. Finite automata and their decision problems // IBM J. of Research and Development, 1959, 3, № 2. p. 114−125 (Русский перевод: Кибернетический сборник, 1962, № 4, с. 58−91)
  109. Sengoku Н. Minimization of nondeterministic finite automata. Master’s thesis, Kyoto University, 1992.
  110. Salomaa A. On sentential forms of contexs-free grammars, Acta Inform. 2 (1973)40−49.
  111. Shankar P., Dasgupta A., Deshmukh K. and Rajan B.S. On viewing block codes as finite automata. Theoretical Computer Science, 290, 3 (2003), 1775−1797.
  112. Tamm H. On Minimality and Size Reduction of One-Tape and Multitape Finite Automata// University of Helsinki, Helsinki, 2004. heory 34, 5 (1988), 1049−1053.
  113. Tamm H. and Ukkonen. E. Bideterministic automata and minimalrepresentations of regular languages. In Proceedings of the CIAA 2003, Lecture Notes in Computer Science 2759, Springer, 2003, 61−71.
  114. Tamm H. and Ukkonen. E. Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science, 328, 1−2(2004), 135−149.
  115. Tamm, H., Nykanen M. and Ukkonen, E. Size Reduction of Multitape Automata. In Proceedings of the CIAA 2005, Lecture Notes in Computer Science, Springer, 2005, 236−244.
  116. L.G.Valiant, The equivalence problem for deterministic finite-turn pushdawn automata, Inform, and Control. 25 (1974) 123−133.
  117. Watson, B.W. Taxonomies and toolkits of regular language algorithms. PhD dissertation, Faculty of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, The Netherlands,
  118. Yamasaki, On multitape automata. In Proceedings of MFCS'79, Lecture Notes in Computer Science 74, Springer, 1979, 533−541.
  119. Zakharov V., Zakharyaschev I. On the equivalence-checking problem for a model of programs related with multi-tape automata // Lecture Notes in Computer Science, v. 3317, 2005, p. 293−304.of Mathematics and Computing Science,
Заполнить форму текущей работой

Сессия? Спокойно!