- Об институте
- Инновации
- Структура
- Отдел "Архитектуры вычислительных систем"
- Отдел "Информационных систем"
- Отдел "Компиляторных технологий"
- Отдел "Системного программирования"
- Отдел "Системной интеграции и прикладных программных комплексов"
- Отдел "Теоретической информатики"
- Отдел "Технологий программирования"
- Ученый совет
- Диссертационный совет
- Центр верификации ОС Linux
- Исследовательский центр доверенного искусственного интеллекта
- Центр компетенции по параллельным и распределенным вычислениям
- Образование
- Издания
- Новости
- Лицензии
О сложности проблемы эквивалентности в модели программ с перестановочными и монотонными операторами.
О сложности проблемы эквивалентности в модели программ с перестановочными и монотонными операторами.
Авторы
Захаров В.А., Захарьящев И.М.
Аннотация
В настоящей заметке предлагается новый алгоритм проверки эквивалентности программ с перестановочными операторами, сохраняющими значение <истина> всех базовых предикатов. Этот алгоритм имеет полиномиальную сложность. Он получен в результате успешного применения одного общего подхода к построению <быстрых> алгоритмов распознавания эквивалентности, предложенного одним из авторов.
Издание
Материалы VIII Международного семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.), 2004, Изд-во механико-математического ф-та МГУ Москва, с. 131-134.