Finite state automata in the theory of algebraic program schemata
https://doi.org/10.15514/ISPRAS-2015-27(2)-10
Abstract
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.
References
1. Podlovchenko R.I. Ierarchiya modeley program [Hierarchy of program models]. Programmirovanije [Programming and Computer Software], 1981, № 2, p. 3-14 (in Russian).
2. Lyapunov A.A. O logicheskih shemah program [On the logical program schemata]. Problemy Kibernetiki [Problems of Cybernetics] Mosocow. Physmathgiz, vol. 1, 1958, p. 46-74 (in Russian).
3. Glushkov V.M., Letichevsky A.A. Teoriya discretnyh preobrazovateley [Theory of discrete transducers] Izbranniye voprosy algebry i logiki [Selected issues in algebra and logics] Novosibirsk, 1973, p. 5-39 (in Russian).
4. Podlovchenko R.I. On one equivalence checking technique for algebraic models of programs Programming and Computer Software, 2011, vol. 37, № 6, p. 292-298.
5. Rabin M.O., Scott D. Finite automata and their decision problems. IBM Journal of Research and Development, 1959, vol.3, №2, p. 114-125.
6. Rutledge J.D. On Ianovs program schemata. Journal of the ACM, 1964, vol. 11, № 1, p. 1-9.
7. Podlovchenko R.I. Equivalent transformations in mathematical models of computations. Tetxbook, Moscow, CMC Faculty, Lomonosov Moscow State University, 2011, 72 p. (in Russian)
8. Podlovchenko R.I. On program schemes with commuting and monotone operators. Programming and Computer Software, 2003, vol. 29, № 5, p. 270-276.
Review
For citations:
Podlovchenko R.I. Finite state automata in the theory of algebraic program schemata. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(2):161-172. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(2)-10
Email this article 