skip to main content
Lingue:

Difference Constraints: An adequate Abstraction for Complexity Analysis of Imperative Programs

Sinn, Moritz ; Zuleger, Florian ; Veith, Helmut

Fulltext disponibile

Citazioni Citato da
  • Titolo:
    Difference Constraints: An adequate Abstraction for Complexity Analysis of Imperative Programs
  • Autore: Sinn, Moritz ; Zuleger, Florian ; Veith, Helmut
  • Note di contenuto: Difference constraints have been used for termination analysis in the literature, where they denote relational inequalities of the form x' <= y + c, and describe that the value of x in the current state is at most the value of y in the previous state plus some integer constant c. In this paper, we argue that the complexity of imperative programs typically arises from counter increments and resets, which can be modeled naturally by difference constraints. We present the first practical algorithm for the analysis of difference constraint programs and describe how C programs can be abstracted to difference constraint programs. Our approach contributes to the field of automated complexity and (resource) bound analysis by enabling automated amortized complexity analysis for a new class of programs and providing a conceptually simple program model that relates invariant- and bound analysis. We demonstrate the effectiveness of our approach through a thorough experimental comparison on real world C code: our tool Loopus computes the complexity for considerably more functions in less time than related tools from the literature. Comment: This is the extended version of our paper published at FMCAD 2015
  • Soggetti: Computer Science - Programming Languages
  • Tipo: Articolo
  • Identificativo: Arxiv ID: 1508.04958
  • Fonte: Cornell University

Ricerca in corso nelle risorse remote ...