The author proposes a logically complete system of transformation rules that preserve tree equivalence, and presents a polynomial-time algorithm for deciding the tree equivalence of linear polyadic recursion schemes, which runs in time O ( n6 ) . Ultimately, the tree equivalence problem for the given scheme is reduced to a global flow analysis problem which, in turn, is solved by an efficient marking algorithm. Extensions to quasilinear schemes are discussed, as are connections to context-free grammars and deterministic pushdown automata.
