Фрагментные преобразования структуры многоленточных автоматов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Великая, Яна Геннадьевна
- Специальность ВАК РФ05.13.17
- Количество страниц 169
Оглавление диссертации кандидат технических наук Великая, Яна Геннадьевна
Введение.
Глава 1. Основные понятия и постановка задач.
1.1 Многоленточные автоматы.
1.2 Фундаментальные проблемы многоленточных автоматов.
1.3 Область применения автоматов.
1.3.1 Формальное проектирование программного обеспечения.
1.3.2 Разработка цифровых устройств.
1.3.3 Лексический анализ.
1.3.4 Компьютерная лингвистика.
1.3.5 8\укс11-технология.
1.3.6 Специализированные языки программирования.
1.4 Единый подход решения фундаментальных проблем.
Глава 2. Фрагментные преобразования.
2.1 Основные понятия.
2.2 Система преобразований Т.
2.3 Полнота системы Т.
Глава 3. Проблема эквивалентности многоленточных автоматов.
3.1 Трансформационный метод.
3.2 Модификация трансформационного метода.
3.3 Решение проблемы эквивалентности многоленточных автоматов, модифицированным трансформационным методом.
3.3.1 Конечные автоматы.
3.3.2 Однородные автоматы.
Глава 4. Проблема минимизации и её решение для некоторых множеств многоленточных автоматов.
4.1 Общее описание процедуры минимизации.
4.2 Минимизация по сложным элементам.
4.3 Минимизация по простым элементам.
4.4 Окончательная минимизация.
4.5 Алгоритмы минимизации.
4.6 Сравнение алгоритмов минимизации.
4.7 Применение многоленточных автоматов в многопроцессорных системах.
Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Структурный анализ многоленточных автоматов2008 год, доктор физико-математических наук Хачатрян, Владимир Ервандович
Нечеткие интервальные модели функциональных систем1998 год, доктор физико-математических наук Шестаков, Александр Анатольевич
Проблемы оптимизации обобщенных конечно-автоматных моделей с периодически меняющейся структурой1999 год, кандидат физико-математических наук Пономарева, Александра Юрьевна
Применение итераций конечных языков в алгоритмических задачах теории формальных языков2012 год, кандидат физико-математических наук Алексеева, Анна Геннадьевна
Универсальное тестирование в частных классах автоматов2007 год, кандидат физико-математических наук Пономаренко, Александр Владимирович
Введение диссертации (часть автореферата) на тему «Фрагментные преобразования структуры многоленточных автоматов»
В связи с развитием информационных технологий и созданием новых языков программирования актуальными остаются задачи, связанные с разработкой трансляторов, для перевода программ с одного языка на другой.
Для реализации отдельных фаз трансляции программы используют известные модели: формальные грамматики, конечные автоматы Мура и Мили, автоматы с магазинной памятью и т.д. Данные модели являются хорошо изученными и применяемыми в области информатики, связанной с теорией обработки формальных языков[1].
Весомый вклад в развитие теории конечных автоматов внесли Глушков В.М., Бернштейн Л.С.,Скляров В.А.,Баранов С.И.Драхтенброт Б. А., Бауэр В., Мили Г., Мур Э., Гилл А., Хаффмен Д., Ауфенкамп Д., Шеннон К. и др. В исследованиях ученых решены вопросы, связанные с проблемой минимизации, проблемой эквивалентности и эквивалентных преобразований конечных автоматов. В работе В.М.Глушкова разработаны теоретическая база для решения задач, возникающих при синтезе цифровых автоматов [2]. Кроме конечного автомата известна модель многоленточного автомата, которая является расширением обычного конечного автомата. В многоленточном автомате в отличие от конечного автомата работа производится на нескольких лентах. Теория многоленточных автоматов развивалась отечественными и зарубежными учёными Подловченко Р.И., Хачатряном В.Е., Летичевским А.А, Бёрдом Р., Гриффитсом Т., Харыо Т., Кархумаки Дж., Тамм X. и др.
Для многоленточных автоматов решены проблемы эквивалентности [3] и эквивалентных преобразований [4]. Однако, при решении конкретных практических задач, требуется рассмотрение лишь определенных подклассов многоленточных автоматов, следовательно, актуальной остается задача разработки систем эквивалентных преобразований для подклассов многоленточных автоматов. Проблема минимизации многоленточных автоматов остаётся открытой. Существуют решения этой проблемы для отдельных подклассов многоленточных автоматов. Из литературных источников известно применение многоленточных автоматов для реализации специализированного языка запросов к базам данных [5].
Диссертационная работа «Фрагментные преобразования структуры многоленточных автоматов», в которой решается вопрос развитию теории многоленточных автоматов для решения задач оптимизации промежуточного представления программ, представленных в виде многоленточных автоматов.
Работа связана с развитием общенаучных направлений РФ и поддержана грантом ФЦП "Научные и научно-педагогические кадры инновационной России на 2009-2013 годы", ГК №16.740.11.0045 от 01.09.2010 г.
Целью настоящей работы является развитие теоретических основ минимизации многоленточных автоматов для повышения эффективности преобразования информационных структур.
Для достижения поставленной цели были сформулированы и решены следующие задачи:
1. разработать систему эквивалентных фрагментных преобразований в подклассе многоленточных автоматов и доказать её полноту;
2. обобщить трансформационный метод решения проблемы эквивалентности для подклассов многоленточных автоматов;
3. решить обобщенную проблему минимизации для подкласса многоленточных автоматов;
4. разработать алгоритмы и программы минимизации многоленточных автоматов;
5. исследовать временную сложность полученных алгоритмов.
Объектом исследования диссертационной работы являются трансляторы специализированных языков запросов к базам данных.
В качестве предмета исследования рассматривался многоленточный автомат.
Методы и средства исследований. При решении указанных задач использовались методы исследования из теории автоматов, математической логики, теории алгоритмов, математическое моделирование, интегрированные среды разработки программ.
Положения, выносимые на защиту:
1. Полная система фрагментных эквивалентных преобразований для подкласса многоленточных автоматов.
2. Модификация трансформационного метода, позволяющая решить проблему эквивалентности для однородных многоленточных автоматов;
3. Автоматизированная система минимизации для подкласса многоленточных автоматов, включающая процедуру минимизации, алгоритмы и комплекс программ.
Научная новизна состоит в:
1. разработке новой системы эквивалентных преобразований для подкласса многоленточных автоматов;
2. формулировке и доказательстве теоремы о полноте предложенной системы эквивалентных преобразований;
3. модификации трансформационного метода для решения проблемы эквивалентности в подклассах многоленточных автоматов;
4. разработке алгоритмов минимизации для подкласса многоленточных автоматов.
Практическая полезность работы заключается в следующем:
1. в реализации результатов диссертации при проектировании интерпретатора специализированного языка запросов автоматизированной системы дистанционной передачи радиолокационных измерений с приёмного устройства на спецвычислитель, внедрённой в ООО «Научно-производственное предприятие «Энергетические и информационные технологии» Белгородского государственного университета».
2. разработаны алгоритмы процедуры минимизации для подмножества многоленточных автоматов, использованные при выполнении фундаментальных исследований, выполненных в рамках тематического плана НИР ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), проект «Методы и алгоритмы преобразования структурированного представления модели управления последовательностью процессов, наделенных частично-коммутативными свойствами», 2010-2012 гг.
3. в использовании результатов диссертационной работы в учебном процессе кафедры математического и программного обеспечения информационных систем ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), при подготовке студентов по специальности 010503 «Математическое обеспечение и администрирование информационных систем», в дисциплине «Теория вычислительных процессов и структур», при обучении студентов по направлению подготовки 010300.68 «Математика. Компьютерные науки», в дисциплине «Теоретическая информатика».
ПЕРВАЯ ГЛАВА посвящена рассмотрению областей информатики, в которых нашли своё применение конечные и многоленточные автоматы. Освещаются фундаментальные достижения и проблемы теории автоматов. Обоснована потребность развития теории многоленточных автоматов в целях их применения при реализации специализированных языков запросов к базам данных.
ВТОРАЯ ГЛАВА посвящена разработке полной системы эквивалентных фрагментных преобразований для подкласса многоленточных автоматов Ь.
Многоленточный автомат задают в виде размеченного ориентированного графа. Фрагмент многоленточного автомата задают некоторым подмножеством вершин графа. Фрагментным преобразованием [6] многоленточного автомата называют замену в автомате одного фрагмента на другой, при этом исходный многоленточный автомат преобразуется в другой многоленточный автомат.
Многоленточный автомат (7 принадлежит подкласса Ь, если он задается графом, вершины которого помечены символами алфавита Р={р,Ц1,.^п.1}, а рёбра символами алфавита ()={0,1}. Из вершин, помеченных символами Чь—^п-и может выходить только одно ребро с меткой 0. Предложенная система эквивалентных преобразований содержит два преобразования, доказана полнота системы в подклассе многоленточных автоматов Ь.
ТРЕТЬЯ ГЛАВА посвящена решению проблемы эквивалентности в некоторых подмножествах многоленточных автоматов с использованием трансформационного метода, который предназначен для решения проблемы эквивалентности многоленточных автоматов. Метод основан на использовании фрагментных эквивалентных преобразований многоленточных автоматов.
Проблема эквивалентности для данного множества объектов заключается в нахождении алгоритма, который по любой паре объектов рассматриваемого множества устанавливает или опровергает факт их эквивалентности.
Нами предложена модификация трансформационного метода.
Доказывается, что модифицированный трансформационный метод решает проблему эквивалентности для конечных и однородных многоленточных автоматов.
В ЧЕТВЕРТОЙ ГЛАВЕ решается проблема минимизации для подкласса многоленточных автоматов Ь и разработке алгоритмов, реализующих процедуру минимизации.
Проблема минимизации в подклассе многоленточных автоматов заключается в том, чтобы по исходному многоленточному автомату найти эквивалентный ему автомат с наименьшим количеством состояний.
Классом эквивалентности называют подмножество всех эквивалентных между собой автоматов.
В литературных источниках показано, что в некоторых подмножествах многоленточных автоматов минимальный автомат находится неоднозначно, т.е. в одном классе эквивалентности может существовать несколько автоматов с минимальным количеством состояний. Притом, что в одном и том же классе эквивалентности может существовать бесконечное множество тупиковых автоматов, т.е. не содержащих эквивалентных состояний и не являющихся минимальными. Таким образом, проблема минимизации для некоторых подмножеств многоленточных автоматов сводится к нахождению нескольких минимальных автоматов, а наличие тупиковых автоматов не дает применить подход, используемый при нахождении минимального конечного автомата. Стоит отметить, что проблема минимизации для множества многоленточных автоматов является открытой и получены решения лишь для отдельных подмножеств.
Для многоленточных автоматов из подкласса Ь предлагается процедура минимизация, которая по данной многоленточному автомату находит все минимальные в одном классе эквивалентности. Разработаны алгоритмы , реализующие процедуру минимизации. Проведено сравнение разработанных алгоритмов с известными алгоритмами [47]. Отметим, что идея и технология решения проблемы минимизации почерпнута из литературных источников[46;64], в которых предложена процедура минимизации для подкласса двухленточных автоматов (алфавит Р={р,ц}). В работе предлагается процедура минимизации для подкласса многоленточных автоматов Ь (алфавит Р={р>Чь—>с1п-1})' Для предоженной процедуры разработаны алгоритмы и комплекс программ. Показан пример применения многоленточных автоматов в многопроцессорных системах.
Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Разработка микропрограммных методов синтеза структур параллельных вычислительных устройств1984 год, кандидат технических наук Пискунов, Сергей Владиславович
Регуляризация контекстно-свободных грамматик на основе эквивалентных преобразований синтаксических граф-схем2009 год, кандидат технических наук Федорченко, Людмила Николаевна
Базисные конечные автоматы2014 год, кандидат наук Мельникова, Александра Александровна
Применение имитационной нормализации в гибридных алгоритмах2012 год, кандидат физико-математических наук Эйрих, Станислав Николаевич
Разработка графовых моделей автоматизированного проектирования абстрактного этапа блочной реализации систем логического управления2007 год, кандидат технических наук Дзугкоева, Анна Альбертовна
Заключение диссертации по теме «Теоретические основы информатики», Великая, Яна Геннадьевна
Заключение
Перечислим основные результаты и выводы, полученные в диссертации:
1. Предложена система фрагментных эквивалентных преобразований для подкласса многоленточных автоматов Ь.
2. Сформулирована и доказана теорема о полноте предложенной системы фрагментных эквивалентных преобразований.
3. Предложена модификация трансформационного метода, нацеленного на решение проблемы эквивалентности многоленточных автоматов.
4. Сформулирована и доказана теорема о том, что предложенная модификация позволяет решить проблему эквивалентности для однородных многоленточных автоматов.
5. Предложена процедура нахождения всех минимальных автоматов в классе эквивалентности для подкласса многоленточных автоматов Ь .
6. Разработаны алгоритмы процедуры минимизации для подкласса многоленточных автоматов Ь и предложена их программная реализация, что позволяет автоматизировать процесс сокращения состояний автомата.
7. В результате проведения вычислительных экспериментов на примерах показано, что предложенный в работе алгоритм имеет выигрыш в быстродействии по сравнению с известным алгоритмом, если он применяется к многоленточным автоматам с большим количеством лент и большим числом символов алфавита, над которым работает многоленточный автомат при сравнительно небольшом числе состояний.
8. Использование многоленточных автоматов разработанной структуры, позволяет в многопроцессорных системах повысить коэффициент загрузки процессоров и быстродействие выполнения информационных преобразований в трансляторах и системах управления базами данных.
Список литературы диссертационного исследования кандидат технических наук Великая, Яна Геннадьевна, 2011 год
1. Хантер Р. Основные концепции компиляторов. Москва: Издательский дом «Вильямс».2002. с.256.
2. Глушков В.М. Синтез цифровых автоматов.- М.:Физматгиз, 1962.-476 с.
3. Хачатрян B.E. Полная система эквивалентных преобразований для многоленточных автоматов // Программирование. 2003. №1. С.62-77.
4. Hakli, R., Nykanen, М., and Tamm, Н. A declarative programming system for manipulating strings. In Sixth Fenno-Ugric Symposium on Software Technology, Sagadi, Estonia, 1999, 29-40.
5. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314
6. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159.
7. Rabin М.О., Scott D. Finite automata and their decision problems // IBM J. of Research and Development, 1959, 3, № 2. p. 114125 (Русский перевод: Кибернетический сборник, 1962, № 4, с. 5891)
8. 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.
9. Elgot C.C. and Mezei J.E. On relations defined by generalized finite automata. IBM J. Res. Develop. 9, (1965), 47-68.
10. Fischer P.C., and Rosenberg, A.L. Multitape one-way nonwriting automata. J. Comput. System Sci. 2, (1968), 88-101.
11. Rabin M.O., Scott D. Finite automata and their decision problems // IBM J. of Research and Development, 1959, 3, № 2. p. 114125.
12. Griffiths T.V. The insolvability of the equivalence problem for D-free nondeterministic generalized machines. J. ACM, 15,3 (1968), 409413.
13. М.Подловченко Р.И. Алгоритм канонизации пар схем программ сперестановочными операторами // Программирование, 1997, № 6,с.316.
14. Подловченко Р.И. К вопросу об эквивалентных преобразованиях алгоритмов и программ // Математические вопросы кибернетики, М., Физматлит, 2000, вып. 9, с. 2536.
15. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314
16. Подловченко Р.И. Проблема эквивалентных преобразований в модели программ с перестановочными и монотонными операторами // Программирование, 2002, №6, с. 117.
17. Подловченко Р.И. О построении полных систем эквивалентных преобразований схем программ // Труды XII Международн. конф.
18. Дискретные модели в теории управляющих систем», М., Диалог-МГУ, 1997, с. 4647.
19. Подловченко Р.И. Система преобразований, полная в классе схем программ с перестановочными операторами // Программирование. 1998. № 2. С. 5867.
20. Подловченко Р.И., Айрапетян М.Г. О построении полных систем эквивалентных преобразований схем программ // Программирование, 1996. № I.e. 329.
21. Хачатрян В.Е. Однородные логические графы // Прикладная математика, изд-во Ереванского гос. университета. Ереван. 1981. с. 6780.
22. Подловченко Р. И., Хачатрян В. Е., Чашин Ю. Г. Полная система эквивалентных преобразований для двухленточных автоматов с непересекающимися циклами // Программирование. 2000. №5. с.119.
23. Яблонский C.B. «Эквивалентные преобразования управляющих систем», Методическая разработка по курсу «Элементы кибернетики», МГУ, ВМК, 1986, с. 140.
24. Айзерман М.А., Гусев JI.A., Розоноэр Л.И., Смирнова И.М., Таль A.A. Логика, автоматы, алгоритмы. М.: ГИФМЛ, 1963.-556 с.
25. ГлушковВ.М. Синтез цифровых автоматов.- М.:Физматгиз, 1962.-476 с.
26. Кобринский H. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. —М.: Физматгиз, 1962. —404 с.
27. Гилл А. «Введение в теорию конечных автоматов», М., Наука, 1970.-272 с.
28. Kinber E. The inclusion problem for some classes of deterministic multitape automata, Theoret.Comput.Sci. 26 (1983), 124.
29. Bird R. The equivalence problem for deterministic two-tape automata // J. of Computer and System Science, 1973, 7, № 4. p. 218236.
30. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности// Программирование. 2004. № 3. С. 117.
31. Хачатрян В.Е. О применении трансформационного метода для распознавания эквивалентности многоленточных автоматов. // VI межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2004. С. 148-150.
32. Хачатрян В.Е. Трансформационные методы сравнения моделей на эквивалентность // Научные ведомости. Серия: информатика, прикладная математика, управление. Белгород. БелГУ. 2004. с. 4051
33. Хачатрян В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4. с. 5255.
34. Подловченко Р.И., Хачатрян В.Е. Алгоритм распознаванияэквивалентности многоленточных автоматов без пересекающихся циклов
35. Труды 5-межд. конф. Дискретные модели в теории управления систем. Ратмино-Москва. 2003. с. 6770.
36. Хачатрян В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4. с. 5255.
37. Хачатрян В.Е., Щербинина Н.В. К вопросу о минимизации в моделях вычислений. // Научные ведомости. БелГУ. Сер. Информатика и прикладная математика, №2(31), вып.З,. 2006. с. 4259.
38. Шишков Д.Б. Минимизация конечных автоматов//Кибернетика. 1972. Том 8. Выпуск 4.с. 297-316.
39. Carrez, С.; On the minimalization of non-deterministic automaton, Laboratoire de Calcul de la Facult.e des Sciences de l'Universit.e de Lille, 1970
40. 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.
41. Jiang T.and Ravikumar В. Minimal NFA problems are hard. SIAM J.Comput. Vol 22, No 6, pages 1117-1141, 1993
42. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159)
43. Носков A.A., Пескова O.B., Ягунова E.B., Большакова Е.И., Клышинский Э.С., Ландэ Д.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистика : учеб. пособие. М:МИЭМ. С.272.
44. Гильмуллин Р.А. Модуль обучающейся модели татарско-турецкого машинного переводчика // Вестник Казанского государственного технического университета им. А.Н.Туполева. 2007, № 2(46) - С. 65-67.
45. André Kempe NLP Applications Based onWeightedMulti-Tape Automata. TALN 2004, Session Poster, Fès, 19-21 avril 2004.
46. Туккель H. И., Шалыто A. A. SWITCH-технология автоматный подход к созданию программного обеспечения «реактивных» систем //Программирование. 2001. № 5, с.45-62.
47. Hakli, R., Nykanen, M., and Tamm, H. A declarative programming system for manipulating strings. In Sixth Fenno-Ugric Symposium on Software Technology, Sagadi, Estonia, 1999, 29-40.
48. Свердлов С.З. Языки программирования и методы трансляции.СПб.: Питер.2007.63 8 с.
49. Хачатрян В.Е., Великая Я.Г. Подход к решению фундаментальных проблем моделей вычислений на примере многоленточных автоматов //Научные ведомости БелГУ. 2009. № 9(64). с. 108-111.
50. Хачатрян В.Е. Об отношениях перестановочности в схемах Янова. // Программирование. 1976. № 4. с. 312.
51. Подловченко Р.И., Айрапетян М.Г. О построении полных систем эквивалентных преобразований схем программ // Программирование, 1996. № I.e. 329.
52. Хачатрян В.Е., Великая Я.Г., Сунцова А.И. Структурные преобразования модели вычислений // Информационные системы и технологии, №3. -2010 г.-с. 45-49.
53. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314.
54. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов (учебное пособие для студентов) М.: Издательский отдел ф-та ВМиК МГУ, 2000 г. - 58 с.
55. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-429 с.
56. Подловченко Р.И, Хачатрян В. Е. Минимальность и тупиковость многоленточных автоматов // Дискретная математика. 2008. № 2. с. 92120.
57. Подловченко Р.И., Хачатрян В.Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд. сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 3843
58. Хачатрян В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН. 2006. том 411. № 3. с. 314318.
59. Великая Я.Г., Хачатрян В.Е. Модификация трансформационного метода//Десятый международный семинар "Дискретная математика и ее приложения". Москва, МГУ. с.447-450.
60. Великая Я.Г. Обобщенный трансформационный метод и конечные детерминированные автоматы // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. №19(90), вып. 16/1, 2010. с.93-103.
61. Хачатрян В.Е. О перестановочности логических графов // Кибернетика. 1976. №3. с. 33-43.
62. Подловченко Р.И., Хачатрян В.Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд. сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 38-43.
63. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности// Программирование. 2004. № 3. С. 117.
64. Хачатрян В.Е. Проблема эквивалентных преобразований для однородных многоленточных автоматов // Программирование. 2008. №3. с. 7780.
65. Sengoku Н. Minimization of nondeterministic finite automata. Master's thesis, Kyoto University, 1992.
66. Watson B.-W. and Daciuk. J. An efficient incremental DFA minimization algorithm. Natural Language Engineering, 9(l):49-64, march 2003.
67. Jiang T.and Ravikumar В. Minimal NFA problems are hard. SIAM J.Comput. Vol 22, No 6, pages 1117-1141, 1993.
68. Kameda Т., Weiner R On the state minimization of nondeterministic automata. IEEE Trans. Comput.c-19, 7(1970),617-627.
69. Hopcroft J. An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-190, Stanford University, 1971.
70. Hopcroft J. E., Motwani R. and Ullman J.D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 2001.
71. Carrez, C.; On the minimalization of non-deterministic automaton, Laboratoire de Calcul de la Facult.e des Sciences de l'Universit.e de Lille, 1970
72. 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.
73. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159.
74. Бауэр В. Введение в теорию конечных автоматов, под ред. Ю.И. Журавлева М.: Радио и связь, 1987. 392 с.
75. Свидетельство о государственной регистрации программы для ЭВМ
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.