“Satisfiability Modulo Extensional Constant Arrays” by Mathias Preiner, Aina Niemetz, and Clark W. Barrett. In Computer Aided Verification - 38th International Conference, CAV 2026, Lisbon, Portugal, July 26-29, 2026, Proceedings, Part II, (Eva Darulova, Anthony W. Lin, and Philipp Rümmer, eds.), 2026, pp. 27-49. Lisbon, Portugal.
Reasoning about array data structures is a key requirement for many applications in hardware and software verification, especially in combination with machine integers. The Satisfiability Modulo Theories (SMT) theory of extensional arrays provides array read and write operators and allows extensionality over arrays. This is sufficient to express many aspects of computer-aided verification, but lacks succinctness to efficiently deal with arrays that are initialized with a default value. Existing procedures for extending the SMT-LIB theory of arrays with support for constant arrays are limited to arrays with infinite index domains, and existing implementations in SMT solvers only support a fragment of the theory for finite index domains. In this paper, we present a novel decision procedure for the theory of arrays with constant arrays that supports arbitrary index domains and is not limited to the infinite case. We present our procedure as an abstract calculus and show its refutational and satisfiability soundness. We implement a decision procedure based on our calculus in the state-of-the-art SMT solver Bitwuzla and evaluate its performance on a diverse collection of benchmarks and use cases.
BibTeX entry:
@inproceedings{PNB26,
author = {Mathias Preiner and Aina Niemetz and Clark W. Barrett},
editor = {Eva Darulova and Anthony W. Lin and Philipp R{\"u}mmer},
title = {Satisfiability Modulo Extensional Constant Arrays},
booktitle = {Computer Aided Verification - 38th International
Conference, {CAV} 2026, Lisbon, Portugal, July 26-29, 2026,
Proceedings, Part {II}},
series = {Lecture Notes in Computer Science},
volume = {16683},
pages = {27--49},
publisher = {Springer},
year = {2026},
doi = {10.1007/978-3-032-32526-6_2},
note = {Lisbon, Portugal},
url = {https://doi.org/10.1007/978-3-032-32526-6_2}
}
(This webpage was created with bibtex2web.)