From transitive closure recursions to single-chain recursions

摘要

A single-chain recursion, whose compiled formula is in a single-chain form, is a generalization of the transitive closure recursion. In this paper the compilation of linear recursions to single-chain recursions is studied by the variable connection graph analysis, which characterizes the linear recursions compilable to single-chain recursions and shows that many seemingly complicated linear recursions are single-chain recursions and can be processed by transitive closure strategies. Moreover, we extend the domain of our study to linear recursions with function symbols and show that many such recursions can also be compiled to single-chain recursions and processed similarly by transitive closure strategies.