О задаче минимизации последовательных программ

Захаров, В.А.; Жайлауова, Ш.Р.

Авторы: Захаров В.А., Жайлауова Ш.Р.
Журнал: Моделирование и анализ информационных систем
Том: 24
Номер: 4
Год издания: 2017
Издательство: Яросл. гос. ун-т
Местоположение издательства: Ярославль
Первая страница: 415
Последняя страница: 433
DOI: 10.18255/1818-1015-2017-4-415-433
Аннотация: Стандартные схемы программ - это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранением отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ с отношением логико-термальной эквивалентности и конечные детерминированные автоматы-преобразователи, работающие над полугруппами подстановок, взаимно транслируются друг в друга. Отсюда следует, что также разрешимы задачи проверки эквивалентности и минимизации для преобразователей указанного вида. Кроме того, на основе обнаруженной взаимосвязи выделен подкласс стандартных схем программ, минимизация которых осуществима за полиномиальное время при помощи ранее известных методов минимизации автоматов-преобразователей, работающих над полугруппами. В заключении приведен пример, свидетельствующий о том, что в общем случае задача минимизации автоматов-преобразователей над полугруппой подстановок может иметь несколько неизоморфных решений.
Добавил в систему: Захаров Владимир Анатольевич

	ИСТИНА	Войти в систему Регистрация
	Интеллектуальная Система Тематического Исследования НАукометрических данных
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

Интеллектуальная Система Тематического Исследования НАукометрических данных

О задаче минимизации последовательных программстатья

Прикрепленные файлы