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

С. 84–87.

Захаров В. А., Жайлауова Ш. Р.

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

Ключевые слова: эквивалентность, минимизация, автомат, minimization problem, substitution, equivalence checking, подстановка, схема программ, finite state automaton, program scheme

В книге

Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.)

М.: МГУ, МАКС Пресс, 2017.