Optimized algorithms for the incremental analysis of logic programs

Puebla Sánchez, Alvaro Germán and Hermenegildo, Manuel V. (1996). Optimized algorithms for the incremental analysis of logic programs. In: "Third International Symposium, SAS '96", September 24 - 26, 1996, Aachen, Germany. ISBN 9783540617396.

Description

Title: Optimized algorithms for the incremental analysis of logic programs
Author/s:
  • Puebla Sánchez, Alvaro Germán
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: Third International Symposium, SAS '96
Event Dates: September 24 - 26, 1996
Event Location: Aachen, Germany
Title of Book: Optimized algorithms for incremental analysis of logic programs
Date: 1996
ISBN: 9783540617396
Volume: 1145
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (921kB) | Preview

Abstract

Global analysis of logic programs can be performed effectively by the use of one of several existing efficient algorithms. However, the traditional global analysis scheme in which all the program code is known in advance and no previous analysis information is available is unsatisfactory in many situations. Incrementa! analysis of logic programs has been shown to be feasible and much more efficient in certain contexts than traditional (non-incremental) global analysis. However, incremental analysis poses additional requirements on the fixpoint algorithm used. In this work we identify these requirements, present an important class of strategies meeting the requirements, present sufficient a priori conditions for such strategies, and propose, implement, and evalúate experimentally a novel algorithm for incremental analysis based on these ideas. The experimental results show that the proposed algorithm performs very efficiently in the incremental case while being comparable to (and, in some cases, considerably better than) other state-of-the-art analysis algorithms even for the non-incremental case. We argüe that our discussions, results, and experiments also shed light on some of the many tradeoffs involved in the design of algorithms for logic program analysis.

More information

Item ID: 14409
DC Identifier: http://oa.upm.es/14409/
OAI Identifier: oai:oa.upm.es:14409
Official URL: http://link.springer.com/chapter/10.1007%2F3-540-61739-6_47?LI=true
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 05 Feb 2013 19:54
Last Modified: 21 Apr 2016 14:03
  • 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