Paper: Homomorphic tree embeddings and their applications to recursive program optimization (at LICS 1993)
Authors: Laks V. S. Lakshmanan Karima Ashraf Jiawei HanAbstract
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
BibTeX
@InProceedings{LakshmananAshrafHan-Homomorphictreeembe, author = {Laks V. S. Lakshmanan and Karima Ashraf and Jiawei Han}, title = {Homomorphic tree embeddings and their applications to recursive program optimization }, booktitle = {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993}, year = 1993, editor = {Moshe Vardi}, month = {June}, pages = {344--353}, location = {Montreal, Canada}, publisher = {IEEE Computer Society Press} }