Compiling general linear recursions by variable connection graph analysis

Research output: Contribution to journalArticlepeer-review


Compilation is a powerful preprocessing technique in the processing of recursions in knowledge‐based systems. This paper develops a method of compiling and optimizing complex function‐free linear recursions using a variable connection graph, the V‐graph. It shows that a function‐free recursion consisting of a linear recursive rule and one or more nonrecursive rules can be compiled to (1) a bounded recursion, in which recursion can be eliminated from the program, or (2) an n‐chain recursion, whose compiled formula consists of one chain, when n= 1, or n synchronized compiled chains, when n > 1. The study is based on a classification of linear recursions and a study of the compilation results of each class. Using the variable connection graph, linear recursions are classified into six classes: acyclic paths, unit cycles, uniform cycles, nonuniform cycles, connected components, and their disjoint mixtures. Recursions in each class share some common properties in compilation. Our study presents an organized picture for the compilation of general function‐free linear recursions. After compilation, the processing of complex linear recursions becomes essentially the processing of primitive n‐chain recursions or bounded recursions to which efficient processing methods are available.

Original languageEnglish (US)
Pages (from-to)12-31
Number of pages20
JournalComputational Intelligence
Issue number1
StatePublished - Jan 1989
Externally publishedYes


  • bases de données déductives
  • compilation techniques
  • deductive databases
  • knowledge‐based systems
  • logic programming
  • programmation logique
  • recursive query processing
  • systèmes à base de connaissances
  • techniques de compilation
  • traitement des requětes récursif

ASJC Scopus subject areas

  • Computational Mathematics
  • Artificial Intelligence


Dive into the research topics of 'Compiling general linear recursions by variable connection graph analysis'. Together they form a unique fingerprint.

Cite this