On the strong equivalence checking for metalinear monadic recursive programs
This paper presents a technique which makes it possible to solve the strong equivalence problem for metalinear monadic recursive program schemata in polynomial time. The main idea is to reduce the strong equivalence problem to the st-connectivity problem by analyzing a special graph which describes the set of all consistent computations for a given pair of programs.