Экзамен по предмету "Теория вычислительных процессов". Билет № 11. 5-й семестр

1. Логико-термальная эквивалентность.
2. Дерево достижимости и анализ свойств сетей Петри на его основе.
Отношение эквивалентности Е, заданное на парах стандартных схем, называют корректным, если для любой пары схем S1 и S2 из S1 Е S2 следует, что S1 S2, т. е. S1 и S2 функционально эквивалентны.
Поиск разрешимых корректных отношений эквивалентности представляет значительный интерес с точки зрения практической оптимизации преобразования программ, поскольку в общем виде функциональная эквивалентность стандартных схем алгоритмически неразрешима.
Идея построения таких (корректных и разрешимых) отношений связанна с введением понятия истории цепочки схем. В истории с той или иной степенью детальности фиксируются промежуточные результаты выполнения операторов рассматриваемой цепочки. Эквивалентными объявляются схемы, у которых совпадают множества историй всех конечных цепочек.

Хорошо, 2012 г