Программная реализация алгоритма нахождения φ-фрагментов

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

Дата регистрации охранного документа:	04.08.2012
№ охранного документа:	2012618964
Автор(ы):	Великая Яна Геннадьевна, Чуев Евгений Викторович, Сунцова Анастасия Игоревна
№ заявки:	2012616879
Дата приоритета:	15.08.2012
Правообладатель:	ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет»
Охранный документ:	Загрузить