Automatic generation of compiled forms for linear recursions

摘要

This article presents a graph-matrix expansion-based compilation technique which compiles complex linear recursions into highly regular compiled forms. The technique uses a variable connection graph-matrix, the V-matrix, to simulate recursion expansions and discover the expansion regularity of complex linear recursions. Our study shows that linear recursions can be compiled into highly regular compiled forms by the V-matrix expansion technique and such compiled forms can be generated automatically. The compilation of linear recursions into compiled forms not only captures the bindings which are difficult to capture otherwise but also facilitates the development of powerful query analysis and evaluation techniques for complex linear recursions in deductive databases.