Статья в сборнике "Математические вопросы кибернетики" №7, Москва, 1998
Авторы:Захаров В.А.
Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах
Аннотация:
В статье исследована проблема эквивалентности для последовательных императивных программ. Семантика этих программ определена посредством интерпретаций (моделей) пропозициональной динамической логики (PDL). В частности, семантика операторов программ задается шкалами PDL. Шкала называется уравновешенной, если для любой пары конечных операторных цепочек результаты их выполнения будут различными, если эти цепочки имеют разную длину. В статье представлена новый униформный метод сведения проблемы эквивалентности программ на уравновешенных шкалах к хорошо известной проблеме тождеств в полугруппах. При помощи этого метода сведения удалось показать, что проблема эквивалентности программ с частично перестановочными операторами разрешима за полиномиальное время.