Efficient Equivalence-Checking Algorithms for Procedural Programs in Progressive Semigroup Gateway Models

Abstract

The problem of program equivalence, checking whether programs have the same (equivalent) behavior in a given model, is investigated. The considered models of programs with “gateway” procedures were proposed somewhat recently, and almost nothing is known about solving the problem of equivalence for them. An approach is proposed to solving the problem of the consistent halting of programs without procedures. Based on known results, it allows to state decidability and polynomial decidability for the equivalence problem with procedures in many gateway models, and the corresponding decision algorithms to be constructed.