George Markowsky
J. Math. Anal. Appl.
Tree equivalence is a relation among polyadic recursion schemes. This relation is broad enough to be interesting: equivalent schemes may not be obviously equivalent and may still differ in computationally important ways. We show that this relation is also narrow enough to imply input-output equivalence. Is tree equivalence decidable? We assign context-free grammars to recursion schemes in such a way that schemes are tree equivalent iff their grammars generate the same language. Known results on LL(k) grammars then imply that tree equivalence is decidable for a class of schemes which includes the monadic recursion schemes without constants. Some important nonmonadic schemes are also included. © 1975 Academic Press, Inc.
George Markowsky
J. Math. Anal. Appl.
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
Matthew A Grayson
Journal of Complexity
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.