Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
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.
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Barry K. Rosen
SWAT 1972