Solving Set Constraints with Comprehensions and Bounded Quantifiers

Mudathir Mohamed \orcid 0000-0002-4644-5756 1 , Nick Feng \orcid 0009-0002-3908-2755 2 , Andrew Reynolds \orcid 0000-0002-3529-8682 1 , Cesare Tinelli \orcid 0000-0002-6726-775X 1 , Clark Barrett \orcid 0000-0002-9522-3084 3 , and Marsha Chechik \orcid 0000-0002-6301-3517 2 · 2025

Read Solving Set Constraints with Comprehensions and Bounded Quantifiers by Mudathir Mohamed \orcid 0000-0002-4644-5756 1 , Nick Feng \orcid 0009-0002-3908-2755 2 , Andrew Reynolds \orcid 0000-0002-3529-8682 1 , Cesare Tinelli \orcid 0000-0002-6726-775X 1 , Clark Barrett \orcid 0000-0002-9522-3084 3 , and Marsha Chechik \orcid 0000-0002-6301-3517 2 (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-08496.txt.

Introduction

Mudathir Mohamed and co-authors solve set limits with bounded quantifiers in a 2025 paper. Many real problems are easy to state as quantified formulas for SMT solvers, programs that check if a set of rules can hold. But solvers often choke on those formulas. The team uses quantifiers that range only over a finite set, a bounded form that fits a filter tool from set theory.

The filter builds a subset of a finite set by testing each member against a rule. On satisfiable problems from a policy tool called SLEEC, this approach beat rival quantifier tricks. On unsatisfiable ones it matched a solver built just for that job. They also mark a class of such limits that can always be decided, and show free use of the filter breaks that promise.

Catalog record

CREATORMudathir Mohamed \orcid 0000-0002-4644-5756 1 , Nick Feng \orcid 0009-0002-3908-2755 2 , Andrew Reynolds \orcid 0000-0002-3529-8682 1 , Cesare Tinelli \orcid 0000-0002-6726-775X 1 , Clark Barrett \orcid 0000-0002-9522-3084 3 , and Marsha Chechik \orcid 0000-0002-6301-3517 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08496

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Set Constraints with Comprehensions and Bounded Quantifiers Mudathir Mohamed \orcid 0000-0002-4644-5756 1 , Nick Feng \orcid 0009-0002-3908-2755 2 , Andrew Reynolds \orcid 0000-0002-3529-8682 1 , Cesare Tinelli \orcid 0000-0002-6726-775X 1 , Clark Barrett \orcid 0000-0002-9522-3084 3 , and Marsha Chechik \orcid 0000-0002-6301-3517 2 Abstract Many real applications problems can be encoded easily as quantified formulas in SMT. However, this simplicity comes at the cost of difficulty during solving by SMT solvers. Different strategies and quantifier instantiation techniques have been developed to tackle this. However, SMT solvers still struggle with quantified formulas generated by some applications. In this paper, we discuss the use of set-bounded quantifiers, quantifiers whose variable ranges over a finite set. These quantifiers can be implemented using quantifier-free fragment of the theory of finite relations with a filter operator, a form of restricted comprehension, that constructs a subset from a finite set using a predicate. We show that this approach outperforms other quantification techniques in satisfiable problems generated by the SLEEC tool, and is very competitive on unsatisfiable benchmarks compared to LEGOS, a specialized solver for SLEEC. We also identify a decidable class of constraints with restricted applications of the filter operator, while showing that unrestricted applications lead to undecidability. I Introduction Problems from many real applications can be encoded naturally in the language of finite sets and relations. Concrete examples include software design specifications [ 15 ] , ontologies [ 17 ] , database queries [ 19 ] , normative requirements [ 12 ] , and authorization policies [ 9 ] . Some SMT solvers support the theory of finite sets and relations [ 1 , 17 ] . Possible encodings in SMT from the applications listed above involve the use of quantifiers with variables that range over elements of some sets with possibly unbounded but finite cardinality. A typical approach is to use standard quantifiers and rely on general quantifier instantiation techniques implemented in SMT solvers. However, solver performance is generally poor in these cases because of the inherent difficulty of reasoning about quantified formulas. The cvc5 solver supports a theory of finite sets and relations that was recently extended with a second-order filter operator [ 19 ] . The filter operator implements a form of set restricted comprehension that constructs a subset from a given set using a given predicate. The extension makes it now possible to express set-bounded quantification using only quantifier-free formulas. This presents an opportunity to encode problems that involve bounded quantification as quantifier-free problem, avoiding the challenges of reasoning with quantifiers. In this paper, we discuss how to encode set-bounded quantifiers in a subtheory of cvc5 ’s theory of finite sets and relations, and present very encouraging initial experimental results that evaluate this encoding on a set of benchmarks from real-world problems. We also discuss the theoretical question on whether there is a reasonably expressive logical fragment with set-bounded quantification with a decidable satisfiability problem. We answer the question positively, but also show that restrictions on the use of the filter operator are not just sufficient but necessary for decidability. This work makes the following contributions : 1. A decision procedure for the satisfiability of a large class of quantifier-free formulas for a theory of finite sets and relations extended with the Cartesian product operator and a filter operator. 2. A high-level proof that the unrestricted use of the filter operator compromises our decidability result. 3. An approach for expressing set-bounded quantifiers in terms of quantifier-free formulas containing applications of the filter operator. 4. Initial empirical results over a set of benchmarks from a real-world application showing that an encoding to SMT using our approach leads to better solver performance compared to encodings using standard quantifiers. I-A Related Work Multi-Level Syllogistic (MLS) theory can be taken as the core fragment for unsorted set theory [ 13 ] . It contains the basic operators \sqcup,\sqcap,\setminus,\sqsubseteq,\approx,\mathrel{\vphantom{\sqsubset}\text{\vtop{\halign{#\cr$\sqsubset$\cr$-$\cr}}}} in addition to logical connectives \vee,\wedge,\neg . Its syntax and semantics consider only sets, with no scalar values, as the latter can be encoded as (nested) sets. A decision procedure based on singleton models 1 1 1 A singleton model is one that assigns each set variable either \varnothing or \{\varnothing\} . was given by Ferro et al. [ 13 ] . The same paper proved the decidability of an MLS extension with map variables 2 2 2 Map variables are binary relations. and operators that return as sets their domains and ranges. Bansal et al. [ 1 ] presented an efficient decision procedure for a natural variant of MLS with a set cardinality operator in the context of many-sorted logic. Meng et al. [ 17 ] extended that theory with operators for finite relations, expressed as finite sets of tuples, that include cross product, relational join, transpose, and transitive closure. They proved the decidability of a small restricted fragment that only accepts binary relations along with relational join and transpose operators. Recently, Mohamed et al. [ 19 ] extended that theory further with filter \sigma and map \pi operators to support reasoning about SQL queries. It can be shown that MLS extended with a set map operator \pi is decidable when its function argument is uninterpreted. This can be achieved by a reduction to the MLS extension with map variables in [ 13 ] . If interpreted functions are allowed in map terms, the fragment is undecidable in general, similarly to the undecidability result we present in Section III-D . Set-bounded quantifiers have been studied extensively for unsorted theories of finite sets. Cantone et al. [ 4 ] showed the undecidability of alternating set quantifiers (\forall\exists)_{0} . Some restricted fragments that are decidable are mentioned in Cantone [ 5 ] . \text{MLSSF}^{\forall} is an example of a decidable fragment that extends MLS with uninterpreted unary functions, singletons, and positive universal bounded quantifiers only with some restrictions on their body expressions. \text{MLSSF}^{\forall} is close in spirit to the decidable fragment we present in Section III for our many-sorted theory of sets, albeit the latter allows existential quantifiers in restricted cases. Cristiá et al. [ 8 ] discussed decidable fragments for “restricted” quantifiers (our “set-bounded” quantifiers): \exists,\forall,\exists\forall , and \forall\exists with no cycles in the “domain graph”. Our calculus and implementation in cvc5 decides the satisfiability of formulas in the first three fragments \exists,\forall,\exists\forall but not in \forall\exists . Currently, it accepts \forall\exists formulas but without termination guarantees. That said, our experimental evaluation does include \forall\exists problems with alternating quantifiers, and our approach works pretty well with those problems. We also note that our calculus supports the cross product operator, which is not mentioned in [ 8 ] . Deciding MLS extended with Cartesian product is reported as an open problem by [ 3 , 5 ] . Cantone and Ursino [ 6 ] proved that MLS with unordered Cartesian product operator but without the set membership operator is decidable in unsorted sets. We prove (see Corollary 1 ) that MLS with membership and Cartesian product operators is decidable in a sorted setting, where all elements of a set have the same sort. II Formal Preliminaries We define our theories and our calculi in the context of many-sorted logic with equality and polymorphic sorts and functions. We

Read the complete text