Homomorphic tree embeddings and their applications to recursive program optimization

Laks V.S. Lakshmanan, Karima Ashraf, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationLogic in Computer Science
PublisherPubl by IEEE
Pages344-352
Number of pages9
ISBN (Print)0818631422
StatePublished - 1993
Externally publishedYes
EventProceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science - Montreal, Quebec, Can
Duration: Jun 19 1993Jun 23 1993

Publication series

NameProceedings - Symposium on Logic in Computer Science

Other

OtherProceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science
CityMontreal, Quebec, Can
Period6/19/936/23/93

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Homomorphic tree embeddings and their applications to recursive program optimization'. Together they form a unique fingerprint.

Cite this