Finite state automata in the theory of algebraic program schemata
Римма Ивановна Подловченко · Proceedings of the Institute for System Programming of RAS · 2015
Algebraic models of programs considered in this paper generalize two models of programs introduced by A.A. Lyapunov and A.A. Letichevsky. The theory of these models focuses on the equivalence checking problem for program schemata which are formalization of imperative programs. We prove that this problem is decidable for a wide class of algebraic models of programs. Our decision techniques are based on the approach to the equivalence checking problem for finite state automata. The aim of this paper is to reveal this relationship.