From transitive closure recursions to single-chain recursions

Research output: Contribution to journalArticlepeer-review


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
Issue number4
StatePublished - 1990
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'From transitive closure recursions to single-chain recursions'. Together they form a unique fingerprint.

Cite this