Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
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.
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Yi Zhou, Parikshit Ram, et al.
ICLR 2023