Efficient top-down set-sharing analysis using cliques

Navas, J. and Bueno Carrillo, Francisco and Hermenegildo, Manuel V. (2006). Efficient top-down set-sharing analysis using cliques. In: "8th International Symposium, PADL 2006", January 9-10, 2006, Charleston, SC, USA. ISBN 978-3-540-30947-5.


Title: Efficient top-down set-sharing analysis using cliques
  • Navas, J.
  • Bueno Carrillo, Francisco
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 8th International Symposium, PADL 2006
Event Dates: January 9-10, 2006
Event Location: Charleston, SC, USA
Title of Book: Practical Aspects of Declarative Languages
Date: 2006
ISBN: 978-3-540-30947-5
Volume: 3819
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

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


Abstract. We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the new abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. We use cliques both as an alternative representation and as widening, defining several widening operators. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efficieney gains are obtained. We also derive useful conclusions regarding the interactions between thresholds, precisión, efficieney and cost of widening. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

More information

Item ID: 14356
DC Identifier: https://oa.upm.es/14356/
OAI Identifier: oai:oa.upm.es:14356
Official URL: http://link.springer.com/chapter/10.1007%2F11603023_13
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 25 Jan 2013 08:46
Last Modified: 21 Apr 2016 13:59
  • 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