Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs

Muthukumar, Kalyan and Hermenegildo, Manuel V. (1990). Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs. Monografía (Technical Report). Facultad de Informática (UPM), Madrid, Spain.

Description

Title: Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs
Author/s:
  • Muthukumar, Kalyan
  • Hermenegildo, Manuel V.
Item Type: Monograph (Technical Report)
Date: April 1990
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of HERME_TCREP_ANDMANS_1990-1.pdf]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

Bruynooghe described a framework for the top-down abstract interpretation of logic programs. In this framework, abstract interpretation is carried out by constructing an abstract and-or tree in a top-down fashion for a given query and program. Such an abstract interpreter requires fixpoint computation for programs which contain recursive predicates. This paper presents in detail a fixpoint algorithm that has been developed for this purpose and the motivation behind it. We start off by describing a simple-minded algorithm. After pointing out its shortcomings, we present a series of refinements to this algorithm, until we reach the final version. The aim is to give an intuitive grasp and provide justification for the relative complexity of the final algorithm. We also present an informal proof of correctness of the algorithm and some results obtained from an implementation.

More information

Item ID: 15292
DC Identifier: https://oa.upm.es/15292/
OAI Identifier: oai:oa.upm.es:15292
Official URL: ftp://clip.dia.fi.upm.es/pub/papers/tr153-90.mcc.p...
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 15 May 2013 07:59
Last Modified: 21 Apr 2016 15:20
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM