Efficient Dataflow Analysis of Logic Programs

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


A framework for efficient dataflow analyses of logic programs is investigated. A number of problems arise in this context: aliasing effects can make analysis computationally expensive for sequential logic programming languages; synchronization issues can complicate the analysis of parallel logic programming languages; and finiteness restrictions to guarantee termination can limit the expressive power of such analyses. Our main result is to give a simple characterization of a family of flow analyses where these issues can be ignored without compromising soundness. This results in algorithms that are simple to verify and implement, and efficient in execution. Based on this approach, we describe an efficient algorithm for flow analysis of sequential logic programs, extend this approach to handle parallel executions, and finally describe how infinite chains in the analysis domain can be accommodated without compromising termination.

Original languageEnglish (US)
Pages (from-to)949-984
Number of pages36
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Jan 10 1992
Externally publishedYes


  • program analysis

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Efficient Dataflow Analysis of Logic Programs'. Together they form a unique fingerprint.

Cite this