## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 12-31 |

Number of pages | 20 |

Journal | Computational Intelligence |

Volume | 5 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1989 |

Externally published | Yes |

## Keywords

- 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