Reachability-based acyclicity analysis by Abstract Interpretation

Genaim, Samir y Zanardini, Damiano (2013). Reachability-based acyclicity analysis by Abstract Interpretation. "Theoretical Computer Science", v. 474 ; pp. 60-79. ISSN 0304-3975. https://doi.org/10.1016/j.tcs.2012.12.018.

Descripción

Título: Reachability-based acyclicity analysis by Abstract Interpretation
Autor/es:
  • Genaim, Samir
  • Zanardini, Damiano
Tipo de Documento: Artículo
Título de Revista/Publicación: Theoretical Computer Science
Fecha: 2013
Volumen: 474
Materias:
Palabras Clave Informales: Abstract Interpretation; Acyclicity Analysis; Termination Analysis; Object-Oriented Programming; Heap Manipulation
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (3MB) | Vista Previa

Resumen

In programming languages with dynamic use of memory, such as Java, knowing that a reference variable x points to an acyclic data structure is valuable for the analysis of termination and resource usage (e.g., execution time or memory consumption). For instance, this information guarantees that the depth of the data structure to which x points is greater than the depth of the data structure pointed to by x.f for any field f of x. This, in turn, allows bounding the number of iterations of a loop which traverses the structure by its depth, which is essential in order to prove the termination or infer the resource usage of the loop. The present paper provides an Abstract-Interpretation-based formalization of a static analysis for inferring acyclicity, which works on the reduced product of two abstract domains: reachability, which models the property that the location pointed to by a variable w can be reached by dereferencing another variable v (in this case, v is said to reach w); and cyclicity, modeling the property that v can point to a cyclic data structure. The analysis is proven to be sound and optimal with respect to the chosen abstraction.

Más información

ID de Registro: 29463
Identificador DC: http://oa.upm.es/29463/
Identificador OAI: oai:oa.upm.es:29463
Identificador DOI: 10.1016/j.tcs.2012.12.018
URL Oficial: http://www.journals.elsevier.com/theoretical-computer-science/
Depositado por: Memoria Investigacion
Depositado el: 18 Jun 2014 10:29
Ultima Modificación: 23 Nov 2017 10:32
  • 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