Efficient management of backtracking in and-parallelism

Hermenegildo, Manuel V. and Nasr, Roger I. (1986). Efficient management of backtracking in and-parallelism. In: "Third International Conference on Logic Programming", July 14-18, 1986, Imperial College of Science and Technology, London, United Kingdom. ISBN 9783540164920.

Description

Title: Efficient management of backtracking in and-parallelism
Author/s:
  • Hermenegildo, Manuel V.
  • Nasr, Roger I.
Item Type: Presentation at Congress or Conference (Article)
Event Title: Third International Conference on Logic Programming
Event Dates: July 14-18, 1986
Event Location: Imperial College of Science and Technology, London, United Kingdom
Title of Book: Third international conference on logic programming
Date: July 1986
ISBN: 9783540164920
Volume: 225
Subjects:
Freetext Keywords: Logic programming, Parallel processing, Intelligent backtracking, and-parallelism, Prolog, Programación lógica, Procesamiento paralelo, Backtracking inteligente.
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 (840kB) | Preview

Abstract

A backtracking algorithm for AND-Parallelism and its implementation at the Abstract Machine level are presented: first, a class of AND-Parallelism models based on goal independence is defined, and a generalized version of Restricted AND-Parallelism (RAP) introduced as characteristic of this class. A simple and efficient backtracking algorithm for R A P is then discussed. An implementation scheme is presented for this algorithm which offers minimum overhead, while retaining the performance and storage economy of sequent ial implementations and taking advantage of goal independence to avoid unnecessary backtracking ("restricted intelligent backtracking"). Finally, the implementation of backtracking in sequential and AND-Parallcl systems is explained through a number of examples.

More information

Item ID: 14534
DC Identifier: http://oa.upm.es/14534/
OAI Identifier: oai:oa.upm.es:14534
Official URL: http://link.springer.com/chapter/10.1007%2F3-540-16492-8_63?LI=true
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 22 Feb 2013 07:35
Last Modified: 21 Apr 2016 14:15
  • 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