On the decidability of the equivalence problem for monadic recursive programs

We present a uniform and easy-to-use technique for deciding the equivalence problem for deterministic monadic linear recursive programs. The key idea is to reduce this problem to the well-known group-theoretic problems by rev ealing an algebraic nature of program computations. We show that the equiva lence problem for monadic linear recursive programs over finite and fixed a lphabets of basic functions and logical conditions is decidable in polynomi al time for the semantics based on the free monoids and free commutative mo noids.AMS Subject Classification. 68Q60.