Paper: Homomorphic tree embeddings and their applications to recursive program optimization (at LICS 1993)

Authors: Laks V. S. Lakshmanan Karima Ashraf Jiawei Han

Abstract

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 Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {344--353},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }