Loading…
Academic Journal
On the application of equivalence checking algorithms for program minimization
V. A. Zakharov, V. V. Podymov
Труды Института системного программирования РАН, Vol 27, Iss 4, Pp 145-174 (2018)
Saved in:
| Title | On the application of equivalence checking algorithms for program minimization |
|---|---|
| Authors | V. A. Zakharov, V. V. Podymov |
| Publication Year |
2018
|
| Source |
Труды Института системного программирования РАН, Vol 27, Iss 4, Pp 145-174 (2018)
|
| Description |
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.
|
| Document Type |
article
|
| Language |
English
Russian |
| Publisher Information |
Ivannikov Institute for System Programming of the Russian Academy of Sciences, 2018.
|
| Subject Terms | |
