Observatorio de I+D+i UPM

Descripción
The Set-Sharing domain has been widely used to infer at compile- time interesting properties of logic programs such as occurs-check reduction, automatic parallelization, and finite-tree analysis. However, performing abstract unification in this domain requires a closure operation that increases the number of sharing groups exponentially. Much attention has been given to mitigating this key inefficiency 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 shV over the finite set of variables of interest V, its negative representation is ℘(V) \ shV . Using this encoding during analysis dramatically reduces the number of elements that need to be represented in the abstract states and during abstract unification as the cardinality of the original set grows toward 2|V| . To further compress the num- ber 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 significantly the memory usage and running time of all abstract operations, including abstract unification.
Internacional	Si
Nombre congreso	24th International Conference on Logic Programming
Tipo de participación	960
Lugar del congreso	Udine, Italy
Revisores	Si
ISBN o ISSN	978-3-540-89981-5
DOI	http://dx.doi.org/10.1007/978-3-540-89982-2_30
Fecha inicio congreso
Fecha fin congreso
Desde la página	301
Hasta la página	316
Título de las actas	Negative Ternary Set-Sharing

Esta actividad pertenece a memorias de investigación

• Participante: Elena Ackley (Universidad de Nuevo Mexico)
• Participante: Jorge Navas Caldente (University of Singapore)
• Autor: Manuel de Hermenegildo Salinas (UPM)
• Participante: Stephanie Forrest (Universidad de Nuevo Mexico)
• Participante: Eric Trias (Universidad de Nuevo Mexico)

• Creador: Grupo de Investigación: Computación lógica, Lenguajes, Implementación y Paralelismo (CLIP)
• Departamento: Inteligencia Artificial