Homomorphic tree embeddings and their applications to recursive program optimization

The problems of stage-preserving linearization and one-boundedness are studied for a class of nonlinear single rule recursive programs, and syntactic characterizations are developed for both. The 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 that does not preserve stages. The class of nonlinear strips that are stage-preserving linearizable includes several classes of programs that can be linearized only using a mix of left and right linear rules, as well as programs that cannot be linearized using previously known techniques. The study makes use of a technique based on the notion of homomorphic tree embeddings