Negative ternary set-sharing

Trias, Eric; Navas, J.; Ackley, Elena S. y Forrest, Stephanie (2009). Negative ternary set-sharing. En: "24th International Conference on Logic Programming", December 9-13 2008, Udine, Italy. ISBN 978-3-540-89981-5.


Título: Negative ternary set-sharing
  • Trias, Eric
  • Navas, J.
  • Ackley, Elena S.
  • Forrest, Stephanie
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 24th International Conference on Logic Programming
Fechas del Evento: December 9-13 2008
Lugar del Evento: Udine, Italy
Título del Libro: Logic Programming
Fecha: 2009
ISBN: 978-3-540-89981-5
Volumen: 5366
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (951kB) | Vista Previa


The Set-Sharing domain has been widely used to infer at compiletime interesting properties of logic programs such as occurs-check reduction, automatic parallelization, and flnite-tree analysis. However, performing abstract uniflcation in this domain requires a closure operation that increases the number of sharing groups exponentially. Much attention has been given to mitigating this key inefflciency in this otherwise very useful domain. In this paper we present a novel approach to Set-Sharing: we define a new representation that leverages the complement (or negative) sharing relationships of the original sharing set, without loss of accuracy. Intuitively, given an abstract state sh\> over the finite set of variables of interest V, its negative representation is p(V) \ shy. Using this encoding during analysis dramatically reduces the number of elements that need to be represented in the abstract states and during abstract uniflcation as the cardinality of the original set grows toward 2 . To further compress the number of elements, we express the set-sharing relationships through a set of ternary strings that compacts the representation by eliminating redundancies among the sharing sets. Our experiments show that our approach can compress the number of relationships, reducing signiflcantly the memory usage and running time of all abstract operations, including abstract uniflcation.

Más información

ID de Registro: 14307
Identificador DC:
Identificador OAI:
URL Oficial:
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Ene 2013 08:37
Ultima Modificación: 21 Abr 2016 13:54
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM