Two efficient representations for set-sharing analysis in logic programs

Trias, Eric and Navas, J. and Ackley, Elena S. and Forrest, Stephanie and Hermenegildo, Manuel V. (2008). Two efficient representations for set-sharing analysis in logic programs. In: "17th Int'l Workshop on Functional and (Constraint) Logic Programming", July 3-4, 2008, Siena, Italy.

Description

Title: Two efficient representations for set-sharing analysis in logic programs
Author/s:
  • Trias, Eric
  • Navas, J.
  • Ackley, Elena S.
  • Forrest, Stephanie
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 17th Int'l Workshop on Functional and (Constraint) Logic Programming
Event Dates: July 3-4, 2008
Event Location: Siena, Italy
Title of Book: 17th International Workshop on Functional and (Constraint) Logic Programming, WFLP'08
Date: July 2008
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 (1MB) | Preview

Abstract

Set-Sharing analysis, the classic Jacobs and Langen's domain, has been widely used to infer several interesting properties of programs at compile-time such as occurs-check reduction, automatic parallelization, flnite-tree analysis, etc. However, performing abstract uniflcation over this domain implies the use of a closure operation which makes the number of sharing groups grow exponentially. Much attention has been given in the literature to mitígate this key inefficiency in this otherwise very useful domain. In this paper we present two novel alternative representations for the traditional set-sharing domain, tSH and tNSH. which compress efficiently the number of elements into fewer elements enabling more efficient abstract operations, including abstract uniflcation, without any loss of accuracy. Our experimental evaluation supports that both representations can reduce dramatically the number of sharing groups showing they can be more practical solutions towards scalable set-sharing.

More information

Item ID: 14595
DC Identifier: http://oa.upm.es/14595/
OAI Identifier: oai:oa.upm.es:14595
Official URL: http://wflp08.dimi.uniud.it
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 06 Mar 2013 07:33
Last Modified: 21 Apr 2016 14:19
  • 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