Институт системного программирования им. В.П. Иванникова РАН


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

Авторы

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

Аннотация

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

Издание

Материалы VIII Международного семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.), 2004, Изд-во механико-математического ф-та МГУ Москва, с. 131-134.

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

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

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