Necessary and sufficient conditions to linearize doubly recursive programs in logic databases
Weining Zhang, Clement T. Yu, Daniel J. Troy · ACM Transactions on Database Systems · 1990
Linearization of nonlinear recursive programs is an important issue in logic databases for both practical and theoretical reasons. If a nonlinear recursive program can be transformed into an equivalent linear recursive program, then it may be computed more efficiently than when the tranformation is not possible. We provide a set of necessary and sufficient conditions for a simple doubly recursive program to be equivalent to a simple linear recursive program. The necessary and sufficient conditions can be verified effectively.