  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.
