Sized Type Analysis for Logic Programs (Technical Communication)

Serrano Mena, Alejandro and López García, Pedro and Bueno Carrillo, Francisco and Hermenegildo, Manuel V. (2013). Sized Type Analysis for Logic Programs (Technical Communication). "Theory and Practice of Logic Programming", v. 13 (n. 4-5 (S); pp. 1-15. ISSN 1471-0684.


Title: Sized Type Analysis for Logic Programs (Technical Communication)
  • Serrano Mena, Alejandro
  • López García, Pedro
  • Bueno Carrillo, Francisco
  • Hermenegildo, Manuel V.
Item Type: Article
Event Title: 29th International Conference on Logic Programming
Event Dates: 24-29 Aug 2013
Event Location: Estambul, Turquía
Título de Revista/Publicación: Theory and Practice of Logic Programming
Date: July 2013
Volume: 13
Faculty: E.T.S. de Ingenieros Informáticos (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 (795kB) | Preview


We present a novel analysis for relating the sizes of terms and subterms occurring at diferent argument positions in logic predicates. We extend and enrich the concept of sized type as a representation that incorporates structural (shape) information and allows expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. For example, expressing bounds on the length of lists of numbers, together with bounds on the values of all of their elements. The analysis is developed using abstract interpretation and the novel abstract operations are based on setting up and solving recurrence relations between sized types. It has been integrated, together with novel resource usage and cardinality analyses, in the abstract interpretation framework in the Ciao preprocessor, CiaoPP, in order to assess both the accuracy of the new size analysis and its usefulness in the resource usage estimation application. We show that the proposed sized types are a substantial improvement over the previous size analyses present in CiaoPP, and also benefit the resource analysis considerably, allowing the inference of equal or better bounds than comparable state of the art systems.

More information

Item ID: 29548
DC Identifier:
OAI Identifier:
Deposited by: Memoria Investigacion
Deposited on: 25 Jul 2014 11:15
Last Modified: 21 Apr 2016 23:56
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM