Программа выделения древовидного покрытия графа

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

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