TY - GEN

T1 - Homomorphic tree embeddings and their applications to recursive program optimization

AU - Lakshmanan, Laks V.S.

AU - Ashraf, Karima

AU - Han, Jiawei

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027287113&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027287113&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027287113

SN - 0818631422

T3 - Proceedings - Symposium on Logic in Computer Science

SP - 344

EP - 352

BT - Logic in Computer Science

PB - Publ by IEEE

T2 - Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science

Y2 - 19 June 1993 through 23 June 1993

ER -