Proceedings of ISP RAS


On the application of equivalence checking algorithms for program minimization

V.A.Zakharov (ISP RAS, Moscow; MSU, Moscow; MIPT, Moscow; HSE, Moscow), V.V.Podymov (MSU, Moscow; HSE, Moscow)

Abstract

Equivalence checking algorithms found vast applications in system programming; they are used in software refactoring, security checking, malware detection, program integration, regression verification, compiler verification and validation. In this paper we show that equivalence checking procedures can be utilized for the development of global optimization transformation of programs. We consider minimization problem for two formal models of programs: deterministic finite state transducers over finitely generated decidable groups that are used as a model of sequential reactive programs, and deterministic program schemata that are used as a model of sequential imperative programs. Minimization problem for both models of programs can be solved following the same approach that is used for minimization of finite state automata by means of two basic optimizing transformations, namely, removing of useless states and joining equivalent states. The main results of the paper are Theorems 1 and 2.
Theorems 1. If G is a finitely generated group and the word problem in G is decidable in polynomial time then minimization problem for finite state deterministic transducers over G is decidable in polynomial time as well.
Theorem 2. If S is a decidable left-contracted ordered semigroup of basic program statements and the word problem in S is decidable in polynomial time then minimization problem for program schemata operating on the interpretation over S is decidable in polynomial time as well.

Keywords

program equivalence, optimizing transformations, reactive program, program scheme, decision procedure

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 4, 2015, pp. 145-174.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(4)-8

Full text of the paper in pdf (in Russian) Back to the contents of the volume