Программа выделения в графе фрагментов с нижней q-границей

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

Дата регистрации охранного документа:	05.09.2012
№ охранного документа:	2012618003
Автор(ы):	Великая Яна Геннадьевна, Чуев Евгений Викторович, Сунцова Анастасия Игоревна
№ заявки:	2012615597
Дата приоритета:	05.07.2012
Охранный документ:	Загрузить