Об одной полугрупповой модели программ, определяемой при помощи двухленточных автоматов.

Об одной полугрупповой модели программ, определяемой при помощи двухленточных автоматов.

Авторы

Захаров В.А., Подымов В.В.

Аннотация

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

Ключевые слова

модель программ, двухленточный автомат, полугруппа

Издание

Научные ведомости Белгородского государственного университета. Серия История, экономика, политология, информатика, 2010, том 14, № 7, с. 94-101.

Научная группа

Теоретическая информатика

Все публикации за 2010 год

Все публикации