Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

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