Encoding and Reasoning About Arrays in Set Theory DOI: XXXXXXX.XXXXXXX CCS: Theory of computation Automated reasoning CCS: Theory of computation Constraint and logic programming CCS: Theory of computation Logic and verification
Maximiliano Cristiá, Gianfranco Rossi · 2025
Read Encoding and Reasoning About Arrays in Set Theory DOI: XXXXXXX.XXXXXXX CCS: Theory of computation Automated reasoning CCS: Theory of computation Constraint and logic programming CCS: Theory of computation Logic and verification by Maximiliano Cristiá, Gianfranco Rossi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11447.txt.
Introduction
Maximiliano Cristiá and Gianfranco Rossi show how to reason about arrays using set theory in a 2025 paper. They encode an array as a function, and a function as a set of ordered pairs. The size of that set matches the length of the array, so array questions become set questions.
The authors define a fragment of set theory rich enough to specify a real class of array programs. They give a decision procedure for that fragment and add it to an existing solver tool where sets and relations are basic types. Users can then reason about sets, functions, and arrays in one language with one solver. The procedure extends earlier ones that lacked array support.
Catalog record
| CREATOR | Maximiliano Cristiá, Gianfranco Rossi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11447
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Encoding and Reasoning About Arrays in Set Theory DOI: XXXXXXX.XXXXXXX CCS: Theory of computation Automated reasoning CCS: Theory of computation Constraint and logic programming CCS: Theory of computation Logic and verification Maximiliano Cristiá, Gianfranco Rossi Abstract . We encode arrays as functions which, in turn, are encoded as sets of ordered pairs. The set cardinality of each of these functions coincides with the length of the array it is representing. Then we define a fragment of set theory that is used to give the specifications of a non-trivial class of programs with arrays. In this way, array reasoning becomes set reasoning. Furthermore, a decision procedure for this fragment is also provided and implemented as part of the { l o g } \{log\} (read ‘setlog’) tool. { l o g } \{log\} is a constraint logic programming language and satisfiability solver where sets and binary relations are first-class citizens. The tool already implements a few decision procedures for different fragments of set theory. In this way, arrays are seamlessly integrated into { l o g } \{log\} thus allowing users to reason about sets, functions and arrays all in the same language and with the same solver. The decision procedure presented in this paper is an extension of decision procedures defined in earlier works not supporting arrays. 1. INTRODUCTION Consider functions as sets of ordered pairs and let \mathit{pfun}(F) be a constraint stating that a set of ordered pairs F is a function. 1 1 1 \mathit{pfun} stands for partial function , thus emphasizing the fact that in this context functions are sets of ordered pairs and not primitive objects as in type theory and functional programming. Hence, the fact that a set of ordered pairs A is an array of length m can be expressed in terms of set theory as follows 2 2 2 Considering that array indexes begin at 1. . (1) arr(A,n)\iff\mathit{pfun}(A)\land|A|=m\land(\forall(x,y)\in A:1\leq x\leq m) A predicate of the form \forall x\in S:\phi , for some set S and formula \phi , is called restricted universal quantifier (RUQ) and is interpreted as \forall x(x\in S\implies\phi) . Now consider a program checking whether or not array A of length m is sorted. bool sorted(A,m) { k := 1; while (k < m && A[k] =< A[k+1]) k := k + 1; return k = m; } If we want to formally verify sorted we can encode array A as a function A satisfying arr(A,m) . 3 3 3 We use verbatim font for programs and math font for specifications. In this way the specification of sorted can be stated in terms of its pre- and post-condition as follows. \displaystyle\textsc{Pre: }arr(A,m) \displaystyle\textsc{Post: }\text{ret}=true\iff\forall(i_{1},x_{1}),(i_{2},x_{2})\in A:i_{1}\leq i_{2}\implies x_{1}\leq x_{2} The post-condition of sorted can be simplified if we introduce the following predicate. (2) \mathit{sorted}(A)\iff\forall(i_{1},x_{1}),(i_{2},x_{2})\in A:i_{1}\leq i_{2}\implies x_{1}\leq x_{2} Furthermore, a good loop invariant to verify sorted is that the left part of A is sorted. In terms of set theory, the left part of an array can be defined by means of the so-called domain restriction operator, noted \dres ( Spivey 1992 ) . (3) I\dres A=\{(x,y)\mid(x,y)\in A\land x\in I\} Note that if A is an array of length m and k\leq m then [1,k]\dres A is also an (smaller) array 4 4 4 [k,m] denotes the closed integer interval from k to m . . Now the loop invariant can be given as follows. (4) \textsc{Inv: }\mathit{sorted}([1,k]\dres A) It is easy to see that domain restriction can be put in terms of basic set operators and RUQ ( N is an existential variable) 5 5 5 This is one of the many ways in which domain restriction can be written. . (5) B=I\dres A\iff A=B\cup N\land(\forall(x,y)\in B:x\in I)\land(\forall(x,y)\in N:x\notin I) Domain restriction is a key operation when specifying loop invariants of programs with arrays as most often loops process arrays from left to right thereby establishing the desired property on the left part of the array as the loop progresses. In summary, an approach to reason about programs with arrays needs to be able to reason about functions as set of ordered pairs, set cardinality, integer intervals and RUQ. RUQ are important because in the specifications of these programs, in many cases, it will be necessary to state properties about all the components of the arrays. Moreover, if we want to be able to automatically reason about these programs we would need to find decision procedures for the theory outlined above. In a previous work ( Cristiá and Rossi 2024a ) we have shown a decision procedure for the Boolean algebra of finite sets extended with set cardinality, integer intervals and linear integer arithmetic. We have also provided a decision procedure for a certain fragment of a theory including RUQ ( Cristiá and Rossi 2024b ) . In this paper we provide a decision procedure for a combination of these theories thus allowing us to automatically reason about a class of programs with arrays—including, for instance, the one just mentioned. In this way, reasoning about arrays becomes reasoning about sets, set cardinality, functions (as set of ordered pairs) and integer intervals. Furthermore, many standard set and relational operators (e.g., domain restriction) can be used to give the specifications and loop invariants of these programs. This should be particularly helpful for users of set-based notations such as B ( Abrial 1996 ; Abrial 2010 ) and Z ( Spivey 1992 ) because in this way they can include arrays in their specifications and reason about them inside the same theoretical framework. Moreover, all the theory and practice already developed by us for other fragments of set theory (e.g., ( Dovier et al. 2000 ; Cristiá and Rossi 2020 ) ) is used here to address arrays. The language and the decision procedure presented in this paper aim at reaching the results presented by Bradley, Manna, and Sipma ( Bradley et al. 2006 ) , perhaps the first in providing a significant decision procedure for arrays. In the end, our results are slightly more powerful than those of Bradley et al. 6 6 6 From now one we will use Bradley as a shorthand for the article by Bradley et al. ( Bradley et al. 2006 ) . because it is possible to reason about more array formulas and it is possible to reason about functions, cardinality and intervals in general. Since that work, others (e.g., ( Habermehl et al. 2008 ) ) have provided decision procedures for more advanced fragments of the theory of arrays. We believe that showing that at least Bradley’s results can be reached from set theory is enough for a first work since, as we just said, this seamlessly integrates arrays into a framework where sets are first-class entities. The new decision procedure is implemented as part of \{log\} (read ‘setlog’) ( Rossi and Cristiá 2000 ) , a constraint logic programming (CLP) language and satisfiability solver where sets and binary relations are first-class entities. The tool is the practical result of our theoretical work carried out over the years on CLP with sets ( Dovier et al. 1996 ; Dovier et al. 2000 ) . Several in-depth empirical evaluations