Программа построения графа с однозначным покрытием

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

Дата регистрации охранного документа:	28.10.2010
№ охранного документа:	2010617196
Автор(ы):	Хачатрян Владимир Ервандович, Великая Яна Геннадьевна, Сунцова Анастасия Игоревна
№ заявки:	2010615479
Дата приоритета:	08.09.2010
Описание изобретения:	Загрузить