Ivannikov Institute for System Programming of the RAS

On the equivalence problem for programs with mode switching.


Podlovchenko R.I., Rusakov D.M., Zakharov V.A.


We study a formal model of imperative sequential programs and focus on the equivalence problem for some class of programs with mode switching whose runs can be divided into two stages. In the first stage a program selects an appropriate mode of computation. Several modes may be tried (switched) in turn before making the ultimate choice. Every time when the next mode is put to a test, the program brings data to some predefined state. In the second stage of the run, once a definite mode is fixed, the final result of computation is produced. We develop a new technique for simulating the behavior of such programs by means of finite automata and demonstrate that the equivalence problem for programs with mode switching is decidable within a polynomial space. By revealing a close relationships between the equivalence problem for this class of programs and the intersection emptiness problem for deterministic finite automata we show that the the former is PSPACE-complete.

Text of article


Proceedings of CIAA-2005 "The 10-th International Conference on Implementation and Application of Automata" (June 27-29, 2005), Sophia Antipolis, France, Lecture Notes in Computer Science, 2006, vol. 3845, pp. 351-352.

Research Group

Theoretical Computer Science

All publications during 2006 All publications