Математические основы информатики и программирования

Эффективные алгоритмы проверки эквивалентности пропозициональных программ Мили на уравновешенных шкалах

В. В. Подымов

МГУ имени М. В. Ломоносова, г. Москва, Россия

Аннотация: Предлагается и рассматривается модель программ, называемая далее моделью пропозициональных программ Мили (ППМ) и представляющая собой небольшое синтаксическое обобщение модели дискретных преобразователей Глушкова  — Летичевского с «осовремененной» семантикой, основанной на понятиях, использующихся в модели пропозициональных последовательных программ, введённой В. А. Захаровым (ПППЗ). Предлагается подход к построению эффективных алгоритмов проверки эквивалентности ППМ, являющийся адаптацией известного подхода к проверке эквивалентности ПППЗ, основанного на анализе графа совместных вычислений программ. Демонстрируется применение этого подхода для получения эффективных алгоритмов проверки эквивалентности ППМ для некоторых видов семантик прикладного характера.

Ключевые слова: проблема эквивалентности, проверка эквивалентности, модели программ, дискретные преобразователи, пропозициональные последовательные программы.

УДК: 519.681:519.71

DOI: 10.17223/20710410/70/5