In this paper we study reducibility of equivalence checking and emptiness problem for program schemata in algebraic models of programs to that for automata. The paper consists of 5 sections. In section 1 we recall the main concepts of algebraic models of programs. In section 2 we present a polynomial time decision procedure for equivalence checking problem in the maximal algebraic model of programs with procedures. In section 3 we show that inclusion problem in algebraic model of programs with procedures can be reduced to inclusion problem in some class of context-free grammars. In section 4 it is shown that inclusion problems for multi-tape automata is two-side reducible to the inclusion problem in some algebraic model of programs without procedures. Finally, in section 5 we consider an algebraic model of programs without procedures such that inclusion problem for two-head automata is reducible to inclusion problem in this algebraic model.

model of programs, program scheme, subroutine, context-free grammar, multi-tape automaton, multi-head automaton, equivalence checking problem, inclusion checking problem, reducibility

Mathematical problems and theory of numerical methods