Глава
О минимизации схем программ относительно логико-термальной эквивалентности
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы покажем, что этим методом можно воспользоваться для минимизации стандартных схем программ относительно л-т эквивалентности в случае, когда эти схемы определены над ортогональными консервативными подстановками.