skip to main content
Lingue:

Complexity and Resource Bound Analysis of Imperative Programs Using Difference Constraints

Sinn, Moritz ; Zuleger, Florian ; Veith, Helmut

Journal of automated reasoning, 2017, Vol.59(1), pp.3-45 [Rivista Peer Reviewed]

Fulltext disponibile

Vedi tutte le versioni
Citazioni Citato da
  • Titolo:
    Complexity and Resource Bound Analysis of Imperative Programs Using Difference Constraints
  • 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 , and describe that the value of in the current state is at most the value of in the previous state plus some constant . We believe that difference constraints are also a good choice for complexity and resource bound analysis because the complexity of imperative programs typically arises from counter increments and resets, which can be modeled naturally by difference constraints. In this article we propose a bound analysis based on difference constraints. We make the following contributions: (1) our analysis handles bound analysis problems of high practical relevance which current approaches cannot handle: we extend the range of bound analysis to a class of challenging but natural loop iteration patterns which typically appear in parsing and string-matching routines. (2) We advocate the idea of using bound analysis to infer invariants: our soundness...
  • Fa parte di: Journal of automated reasoning, 2017, Vol.59(1), pp.3-45
  • Soggetti: Amortized Analysis ; Automatic Complexity Analysis ; Bound Analysis ; Complexity Analysis ; Cost Analysis ; Difference Constraints ; Resource Bound Analysis ; Static Analysis
  • Lingua: Inglese
  • Tipo: Articolo
  • Identificativo: E-ISSN: 1573-0670 ; PMID: 30069066 Version:1 ; DOI: 10.1007/s10817-016-9402-4

Ricerca in corso nelle risorse remote ...