An afficient equivalence-checking algorithm for a model of programs with commutative and absorptive statements

Автор: Vladislav Podymov
Сборник: CEUR Workshop Proceedings
Серия: Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Proceedings. Volume 2
Том: 1492
Год издания: 2015
Место издания: ceur-ws.org
Первая страница: 85
Последняя страница: 96
Аннотация: We present an efficient equivalence-checking algorithm for a propositional model of programs with semantics based on (what we call) progressive monoids on the finite set of statements generated by relations of a specific form. We consider arbitrary set of relations for commutativity (relations of the form ab=ba for statements a, b) and left absorption (relations of the form ab=b for statements a, b) properties. The main results are a polynomial-time decidability for the equivalence problem in the considered case, and an explicit description of an equivalence-checking algorithm which terminates in time polynomial in size of programs.
Добавил в систему: Подымов Владислав Васильевич

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

ИСТИНА