---
_id: '1391'
abstract:
- lang: eng
text: "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.\r\nAFL 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."
alternative_title:
- LNCS
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Andrey
full_name: Kupriyanov, Andrey
id: 2C311BF8-F248-11E8-B48F-1D18A9856A87
last_name: Kupriyanov
citation:
ama: 'Daca P, Henzinger TA, Kupriyanov A. Array folds logic. In: Vol 9780. Springer;
2016:230-248. doi:10.1007/978-3-319-41540-6_13'
apa: 'Daca, P., Henzinger, T. A., & Kupriyanov, A. (2016). Array folds logic
(Vol. 9780, pp. 230–248). Presented at the CAV: Computer Aided Verification, Toronto,
Canada: Springer. https://doi.org/10.1007/978-3-319-41540-6_13'
chicago: Daca, Przemyslaw, Thomas A Henzinger, and Andrey Kupriyanov. “Array Folds
Logic,” 9780:230–48. Springer, 2016. https://doi.org/10.1007/978-3-319-41540-6_13.
ieee: 'P. Daca, T. A. Henzinger, and A. Kupriyanov, “Array folds logic,” presented
at the CAV: Computer Aided Verification, Toronto, Canada, 2016, vol. 9780, pp.
230–248.'
ista: 'Daca P, Henzinger TA, Kupriyanov A. 2016. Array folds logic. CAV: Computer
Aided Verification, LNCS, vol. 9780, 230–248.'
mla: Daca, Przemyslaw, et al. Array Folds Logic. Vol. 9780, Springer, 2016,
pp. 230–48, doi:10.1007/978-3-319-41540-6_13.
short: P. Daca, T.A. Henzinger, A. Kupriyanov, in:, Springer, 2016, pp. 230–248.
conference:
end_date: 2016-07-23
location: Toronto, Canada
name: 'CAV: Computer Aided Verification'
start_date: 2016-07-17
date_created: 2018-12-11T11:51:45Z
date_published: 2016-07-13T00:00:00Z
date_updated: 2023-09-07T11:58:33Z
day: '13'
department:
- _id: ToHe
doi: 10.1007/978-3-319-41540-6_13
ec_funded: 1
intvolume: ' 9780'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1603.06850
month: '07'
oa: 1
oa_version: Preprint
page: 230 - 248
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication_status: published
publisher: Springer
publist_id: '5818'
quality_controlled: '1'
related_material:
record:
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Array folds logic
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9780
year: '2016'
...