Homomorphic tree embeddings and their applications to recursive program optimization

We study the problems of stage preserving linearization and 1-boundedness for a class of nonlinear single rule recursive programs and develop syntactic characterizations for both. Our characterizations lead to a polynomial time algorithm for the former and a linear time algorithm for the latter. Stage preserving linearization results in a significant improvement in evaluation efficiency, compared to a linearization which does not preserve stages. The class of non-linear sirups which are stage preserving linearizable includes several classes of programs which can be linearized only using a mix of left and right linear rules, as well as programs which cannot be linearized using previously known techniques. Our study makes use of a novel technique based on the notion of homomorphic tree embeddings.