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

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

Авторы

Захаров В.А., Захарьящев И.М.

Аннотация

В статье исследуется проблема эквивалентности программ в пропозициональных моделях последовательных операторных программ. Рассматриваемые модели характеризуются двумя параметрами - отношением перестановочности $E$ на множестве базовых операторов и функцией сдвига $J$, указывающей для каждого базового оператора $a$ и каждого значения истинности 0,1 множество всех тех базовых предикатов, которые сохраняют это значение истинности после всякого выполнения оператора $a$. Доказано, что в том случае, когда для любой пары перестановочных операторов функция сдвига принимает одинаковые значения, проблема эквивалентности программ на множестве моделей $M_{E,J}$ разрешима. Эта теорема обобщает ранее известные результаты о разрешимости проблемы эквивалентности программ с перестановочными операторами, сохраняющими значения предикатов.

Издание

Труды 6-ой Международной конференции «Дискретные модели в теории управляющих систем", 7-11 декабря 2004 г., Москва, 2004, МАКС Пресс - МГУ Москва, с. 105-109.

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

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

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

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