💻 computer science

A Decision Procedure for a Theory of Finite Sets with Finite Integer Intervals

This paper presents a decision procedure for the logic $\mathcal{L}_{[\,]}$ , which extends finite set theory with finite integer intervals allowing unbounded variables, and demonstrates its practical utility through the $\{log\}$ tool in automatically verifying invariance lemmas for an elevator algorithm.

Original authors: Maximiliano Cristiá, Gianfranco Rossi

Published 2026-05-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maximiliano Cristiá, Gianfranco Rossi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master organizer trying to manage a very specific kind of warehouse. In this warehouse, you have two types of items: boxes (which can contain other boxes or items) and numbered shelves (which hold a continuous range of integers, like shelves 1 through 10).

For a long time, computer tools could help you organize the boxes perfectly. They could tell you if two boxes were the same, if one box was inside another, or how many items were in a box. However, these tools hit a wall when you tried to talk about the numbered shelves. They couldn't easily reason about a shelf that spans from "floor 3" to "floor 10" while simultaneously checking if a specific box of items was sitting on that shelf.

This paper introduces a new "super-organizer" tool (called {log} or "setlog") that can handle both boxes and numbered shelves at the same time. Here is how the authors achieved this, explained through simple analogies.

1. The Problem: The "Shelf" Gap

Previously, the tool could handle:

Boxes: "Is Box A the same as Box B?" or "How many apples are in Box C?"
Numbers: "Is number 5 less than number 10?"

But it couldn't handle the mix: "Is the collection of items on Shelf [3, 10] (which means shelves 3, 4, 5, 6, 7, 8, 9, and 10) exactly the same as Box A?"

The authors wanted to build a system that could automatically prove things like: "If I split the items on Shelf [3, 10] into two groups, and both groups have the same number of items, then the shelf must have an even number of slots."

2. The Magic Trick: The "Identity Card"

To solve this, the authors discovered a clever mathematical "identity card" (a specific rule) that acts as a translator.

Think of a numbered shelf (an interval like [3, 10]) as a very rigid, pre-packed box. You know exactly what's inside it just by looking at the start and end numbers.

The Rule: If you have a box, and you know two things:
1. Everything in the box fits inside the shelf [3, 10].
2. The box has exactly the right number of items to fill that shelf (in this case, 8 items).
- Then: The box is the shelf. It is identical to the shelf [3, 10].

The authors' tool uses this trick. When it sees a complex question involving a shelf, it doesn't try to solve the "shelf" part directly. Instead, it says, "Okay, let's pretend this shelf is just a regular box with a specific number of items." It translates the "shelf" problem into a "box" problem that the tool already knows how to solve.

3. The "Minimum Solution" Detective

Once the tool translates the shelf into a box, it faces a new challenge: How do we know if a solution is possible without checking every single possibility in the universe?

Imagine you are trying to find the smallest possible group of people that satisfies a rule.

The tool first finds the smallest possible group (the "minimum solution") that fits the rules.
The Logic: If the smallest group fails to satisfy the rule, then any larger group will also fail. It's like trying to fit a giant elephant into a small car; if the car is too small for the elephant, adding more elephants won't help.
Conversely, if the smallest group works, then the rule is satisfied.

By only checking these "minimum" scenarios, the tool avoids getting stuck in an infinite loop of checking every possible combination. It proves that if the simplest case works (or fails), the whole problem is solved.

4. The Elevator Test (The Case Study)

To prove their new tool works in the real world, the authors tested it on a classic problem: The Elevator Algorithm.

Imagine an elevator moving between floors. It has requests (people wanting to go up or down). The tool had to prove that the elevator's logic was safe and correct.

The Challenge: The elevator needs to know things like, "If I am on floor 3 and moving up, and there are requests on floors 5 and 8, which floor do I go to next?" This involves reasoning about a range of floors (intervals) and the set of requests (boxes).
The Result: The tool automatically checked all the rules (invariants) of the elevator system. It proved that the elevator would never get stuck, would always move in the right direction, and would handle requests correctly. It did this without a human having to manually check every single step, proving the system was logically sound.

5. Why This Matters

Before this paper, if you wanted to verify software that deals with both sets of data and ranges of numbers (like arrays in computer programs or time intervals), you often had to do it by hand or use tools that couldn't handle the complexity.

This paper provides a decision procedure. In plain English, this means the tool is a "yes/no" machine that can definitively answer: "Is this statement about sets and number ranges true or false?" It guarantees an answer in a finite amount of time.

Summary

The authors built a bridge between two worlds: Sets (groups of things) and Intervals (ranges of numbers). They did this by:

Creating a rule that turns a "range of numbers" into a "group of items" if the size matches.
Using a "smallest case" strategy to avoid getting lost in infinite possibilities.
Proving it works by successfully automating the safety checks for an elevator system.

The result is a tool that can automatically verify complex logical rules involving both collections of items and continuous number ranges, something that was previously very difficult to do automatically.

Technical Summary: A Decision Procedure for a Theory of Finite Sets with Finite Integer Intervals

Problem Statement

In the context of formal verification and analysis, automated reasoning tools are essential for discharging verification conditions. While existing tools based on set theory (e.g., B, ProB) are effective, they often lack decision procedures for specific fragments of set theory that combine finite sets with integer intervals. Specifically, the Boolean algebra of finite sets extended with cardinality constraints (denoted as $L|\cdot|$ ) is decidable, but it cannot natively express or reason about finite integer intervals (ranges) where limits may be unbounded variables. This limitation hinders the automatic verification of properties involving set operations such as finding the minimum or maximum of a set, partitioning sets based on integer thresholds, or reasoning about array domains defined by intervals. The core problem addressed is the decidability of a theory that integrates finite sets, cardinality constraints, and finite integer intervals (denoted as $L[\ ]$ ) within a quantifier-free logic.

Methodology

The authors propose a decision procedure, SAT $[\ ]$ , which extends the existing solver SAT $|\cdot|$ (for $L|\cdot|$ ) to handle integer intervals. The methodology relies on a base theory of hereditarily finite sets implemented within the Constraint Logic Programming (CLP) language CLP($SET$) and the tool {log}.

Key Technical Components:

Language Extension ( $L[\ ]$ ):
- The language is extended to include set terms of the form $[k, m]$ , representing the set $\{p \in \mathbb{Z} \mid k \le p \le m\}$ .
- Interval limits ( $k, m$ ) can be integer linear terms, including variables.
- The logic remains quantifier-free, utilizing conjunctions and disjunctions of constraints involving set membership, union, disjointness, cardinality, and interval membership.
Core Identity and Reduction Strategy:
- The central theoretical insight is the identity: $k \le m \implies (A = [k, m] \iff A \subseteq [k, m] \land |A| = m - k + 1)$ .
- This identity allows the procedure to transform constraints involving equality with an interval into constraints involving subset relations and cardinality.
- The solver rewrites formulas into a conjunction of a standard $L|\cdot|$ formula ( $\Phi_{|\cdot|}$ ) and a set of subset constraints involving intervals ( $\Phi_{\subseteq[\ ]}$ ), typically of the form $X \subseteq [p, q]$ where $X$ is a variable.
The SAT $[\ ]$ Algorithm:
- Rewrite Rules: The solver employs a set of rewrite rules (STEPS $[\ ]$ ) that reduce syntactic complexity. These rules handle equality, membership, union, disjointness, and cardinality constraints involving intervals.
- Reduction to Integer Arithmetic: Many rules rewrite set constraints involving intervals directly into linear integer arithmetic (LIA) constraints.
- Minimum Solution Check: When irreducible constraints of the form $X \subseteq [p, q]$ $X \subseteq [p, q]$ remain, the procedure does not simply fail. Instead, it leverages the property that if a formula is satisfiable, it must have a "minimum solution" (a solution where sets have the minimum possible cardinality).
  - The solver computes the minimum solution for the $L|\cdot|$ part ( $\Phi_{|\cdot|}$ ).
  - It then checks if this minimum solution satisfies the interval constraints ( $\Phi_{\subseteq[\ ]}$ ).
  - The authors prove that if no minimum solution satisfies the full formula, then no larger solution will either, rendering the formula unsatisfiable.
Implementation in {log}:
- The procedure is implemented in {log} (setlog), a Prolog-based tool.
- The implementation includes a memoizing schema to track variable substitutions for intervals, preventing redundant rewriting and improving efficiency.
- Derived constraints (e.g., intersection, difference) are defined in terms of primitive constraints to maintain consistency.

Key Contributions

Decidability Proof: The paper provides the first proof that the Boolean algebra of finite sets extended with cardinality constraints and finite integer intervals ( $L[\ ]$ ) is decidable.
Decision Procedure (SAT $[\ ]$ ): A complete algorithm is presented that decides the satisfiability of $L[\ ]$ formulas. The procedure is proven to be sound, complete, and terminating.
Integration of Intervals and Sets: Unlike approaches that treat intervals as a separate domain or require constant limits, this work seamlessly integrates variable-bounded integer intervals into set theory, allowing for the expression of non-trivial operators (e.g., $i$ -th smallest element, partitioning by a threshold) in a quantifier-free logic.
Implementation and Tooling: The decision procedure is implemented as an extension of the {log} tool, providing a dual capability as both a constraint logic programming language and a satisfiability solver.

Results and Evaluation

The paper presents empirical evidence and a case study to demonstrate the practical utility of the approach:

Benchmark Evaluation: A set of 60 $L[\ ]$ formulas, representing properties of operators defined in the paper (e.g., minimum, maximum, $i$ -th element), was solved. {log} solved all problems in an average of 0.51 seconds per problem, with only one taking over 5 seconds.
Case Study (Elevator Algorithm): The authors modeled an elevator control system where the elevator must serve requests in a specific direction. The model utilized integer intervals to define floors and requests.
- The system included 7 operations (e.g., adding requests, serving next request).
- {log} was used to automatically discharge 49 invariance lemmas (proving that state operations preserve 7 state invariants) and 7 initial state checks.
- All proofs were completed in approximately 0.5 seconds on a standard laptop.
- The tool successfully generated counterexamples when invariants were intentionally weakened, demonstrating its debugging capabilities.

Significance and Claims

The authors claim that this work represents a significant step forward in automated reasoning for formal verification. By extending the decidable fragment of set theory to include finite integer intervals with variable limits, the approach allows for the automatic verification of properties that were previously difficult or impossible to express without quantifiers.

The paper emphasizes that the approach is rooted in set theory, distinguishing it from other interval reasoning tools (like those based on Allen's interval algebra or static analysis lattices) which often lack the ability to combine intervals with general set operations. The integration of interval reasoning into the {log} framework allows users to write programs and prove their properties using the same code and tool, leveraging the duality of formula and program. The authors modestly note that while the approach is general and coherent, it may incur efficiency costs compared to specialized solvers for specific interval-only problems, but the trade-off is the ability to reason about complex hybrid set-interval structures.