Array folds logic Conference Paper


Author(s): Daca, Przemysław; Henzinger, Thomas A; Kupriyanov, Andrey
Title: Array folds logic
Title Series: LNCS
Affiliation IST Austria
Abstract: We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as "the first array cell contains the array length," and "the array contains equally many minimal and maximal elements." These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability. AFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.
Keywords: Program verification; Decision procedure; Software testing; Computer aided analysis; Reconfigurable hardware; Formal logic; Counter machines; Functional languages; Proof obligations; Satisfiability problems; Theory of integers; Universal quantifiers
Conference Title: CAV: Computer Aided Verification
Volume: 9780
Conference Dates: July 17 - 23, 2016
Conference Location: Toronto, Canada
Publisher: Springer  
Date Published: 2016-07-13
Start Page: 230
End Page: 248
Sponsor: This research was supported in part by the European Research Council (ERC) under grant 267989 (QUAREM) and by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE and SHiNE) and Z211-N23 (Wittgenstein Award).
URL:
DOI: 10.1007/978-3-319-41540-6_13
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Przemysław, Daca
    12 Daca
Related IST Austria Work