Reachability-based acyclicity analysis by Abstract Interpretation

Genaim, Samir and 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.

Description

Title: Reachability-based acyclicity analysis by Abstract Interpretation
Author/s:
  • Genaim, Samir
  • Zanardini, Damiano
Item Type: Article
Título de Revista/Publicación: Theoretical Computer Science
Date: 2013
ISSN: 0304-3975
Volume: 474
Subjects:
Freetext Keywords: Abstract Interpretation; Acyclicity Analysis; Termination Analysis; Object-Oriented Programming; Heap Manipulation
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (3MB) | Preview

Abstract

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.

More information

Item ID: 29463
DC Identifier: http://oa.upm.es/29463/
OAI Identifier: oai:oa.upm.es:29463
DOI: 10.1016/j.tcs.2012.12.018
Official URL: http://www.journals.elsevier.com/theoretical-computer-science/
Deposited by: Memoria Investigacion
Deposited on: 18 Jun 2014 10:29
Last Modified: 23 Nov 2017 10:32
  • 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