О проблеме эквивалентности операторных программ на уравновешенных однородных обратимых шкалах.

Авторы

Захаров В.А.

Аннотация

В данной работе рассматривается класс пропозициональных операторных программ, семантика которых определяется уравновешенными однородными обратимыми моделями пропозициональной динамической логики. Эти модели базируются на разрешимых полугруппах операторов, подчиняющихся законам правого и левого сокращения. Основной результат работы - описание алгоритма, разрешающего эквивалентность указанных программ. В основу алгоритма положен анализ метрических свойств критериальных графов программ. Статья организована следующим образом. Вначале вводятся основные понятия теории пропозициональных операторных программ, позволяющие сформулировать проблему эквивалентности. Затем идет ряд лемм, в которых устанавливаются необходимые и достаточные условия эквивалентности пропозициональных операторных программ на уравновешенных однородных обратимых шкалах. И в заключение предлагается описание алгоритм, разрешающего эквивалентность программ.

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

модель программ, динамические шкалы, проблема эквивалентности, разрешимость, сложность

Издание

Математические вопpосы кибеpнетики, М.: Физматлит, 2001, том 10, с. 134-144.

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

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

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

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