В этой статье исследуются вопросы сводимости проблем эквивалентности и пустоты для различных классов схем программ и автоматов. Статья состоит из пяти разделов. Вначале приводятся определения основных понятий, относящихся к теории алгебраических моделей программ. В разделе 2 представлен полиномиальный по времени алгоритм проверки эквивалентности схем программ с процедурами в максимальной алгебраической модели программ. В разделе 3 показно, что проблема включения в алгебраической модели программ с процедурами может быть сведена к проблеме включения для одного класса контекстно свободных грамматик. В разделе 4 установлено, что проблема включения для многоленточных автоматов сводима к проблеме эквивалентности схем программ в одном специальном классе алгебраических моделей программ без процедур. Наконец, в разделе 5 описан класс алгебраических моделей программ без процедур и показано, что проблема включения для двухголовочных автоматов сводима к проблеме эквивалентности схем программ в указанном классе алгебраических моделей.

модель программ, схема программ, процедура, контекстно-свободная грамматика, монголенточный автомат, двухголовочный автомат, проблема эквивалентности, проблема включения, сводимость

Математические вопросы и теория численных методов