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 -