• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

О проблеме логико-термальной эквивалентности недетерминированных стандартных схем программ

С. 196-198.
Захаров В. А., Попеско У. В.

Стандартные схемы программ были введены для разработки математических методов решения задач трансляции, оптимизации и верификации последовательных операторных программ. Ранее было показано, что логико-термальная эквивалентность аппроксимирует функциональную эквивалентность стандартных схем программ. Другое достоинство логико-термальной эквивалентности состоит в том. что это отношение разрешимо за полиномиальное время. Возникает вопрос: можно уточнить отношение логико-термальной эквивалентности, сохранив при этом ее полиномиальную разрешимость? В статье показано, что проблема логико-термальной эквивалентности для недетерминированных стандартных схем программ алгоритмически неразрешима.