From transitive closure recursions to single-chain recursions

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)479-488
Number of pages10
JournalInformation Systems
Volume15
Issue number4
DOIs
StatePublished - 1990
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this