💻 computer science

Computing Witnesses Using the SCAN Algorithm

This paper extends the saturation-based SCAN algorithm for second-order quantifier elimination to compute witnesses for second-order quantifiers that yield logically equivalent first-order formulas and presents a prototype implementation of the method.

Original authors: Fabian Achammer, Stefan Hetzl, Renate A. Schmidt

Published 2026-05-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fabian Achammer, Stefan Hetzl, Renate A. Schmidt

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 have a complex recipe (a logical formula) that includes a secret ingredient, let's call it "Ingredient X." You don't know what "Ingredient X" is, but you know that if you use some version of it, the recipe works perfectly.

The Problem:
Usually, when logicians want to get rid of "Ingredient X" to see what the recipe actually is without the secret, they use a method called Second-Order Quantifier Elimination (SOQE). This is like trying to describe the final dish without ever mentioning the secret ingredient. Sometimes, you can do this perfectly. But often, the math says, "We can describe the result, but we can't tell you exactly what the secret ingredient was."

The New Discovery (WSOQE):
This paper introduces a new, more ambitious goal called Witnessed Second-Order Quantifier Elimination (WSOQE). Instead of just describing the final dish, the authors want to find the exact recipe for "Ingredient X" (the "witness") that makes the whole thing work. They want to say, "Ingredient X is actually just 'sugar'."

The Tool: The SCAN Algorithm
The authors use a famous tool called the SCAN algorithm. Think of SCAN as a giant, automated kitchen robot that takes your recipe, breaks it down into tiny steps, and tries to remove "Ingredient X" by mixing and matching the other ingredients until the secret is no longer needed.

What This Paper Adds:
The original SCAN robot was great at removing the secret ingredient and telling you the final result, but it threw away the notes on how it did it. It didn't keep the "recipe for Ingredient X."

The authors, Fabian Achammer, Stefan Hetzl, and Renate A. Schmidt, have upgraded the robot (calling the new version WSCAN). Now, as the robot works, it keeps a detailed diary of every step it takes. At the end, it uses this diary to work backward and reconstruct the exact recipe for "Ingredient X."

How They Do It (The "Detective" Analogy):

The Cleanup: The robot starts with a messy pile of clues (clauses). It performs logical moves (like solving a puzzle) to eliminate "Ingredient X."
The Diary: Every time the robot deletes a clue because it's no longer needed, it writes down why it deleted it.
The Reverse Engineering: Once the robot is done and "Ingredient X" is gone, the authors look at the diary. They work backward from the clean result to the messy start. By reversing the logic of the robot's steps, they can build a formula that acts exactly like "Ingredient X."

The "Infinite" vs. "Finite" Problem:
Sometimes, when the robot tries to figure out the recipe for "Ingredient X," the recipe becomes infinitely long (like a story that never ends).

The Fix: The authors found a special condition called "acyclic purification." Imagine a graph where every step in the robot's process is a node. If the graph has no loops (it's "acyclic"), the recipe for "Ingredient X" is guaranteed to be short and finite. If there are loops, the recipe might be infinite.
The Result: They created a method to check if the process is loop-free. If it is, they can produce a simple, finite "first-order" recipe for the secret ingredient. If it's not, they can still produce a recipe, but it might be an infinite one (or a "fixpoint" recipe, which is a fancy way of saying "a recipe that refers to itself to keep going").

Real-World Examples Mentioned:
The paper doesn't just talk theory; they tested their robot on 44 different logic puzzles.

Graph Reachability: They used it to solve a problem about navigating a map. Imagine you have a map with cities and roads, and you want to find a set of cities you can reach starting from City A without hitting City B. The robot successfully found the exact rule (the "witness") that defines which cities are safe to visit.
Equality: They showed the robot can handle rules where things are "equal" (like $a = b$ ), which makes the puzzle harder but the robot still manages to find the secret ingredient's recipe.

The Bottom Line:
This paper takes an existing logic tool (SCAN) that was good at removing unknown variables and upgrades it to not only remove them but also reveal exactly what those variables must have been. It bridges the gap between "finding a solution" and "finding the specific definition of the unknown," providing a prototype implementation that works on real examples, though it admits that sometimes the "recipe" for the unknown might be too complex to write down in a single sentence.

1. Problem Statement

The paper addresses Second-Order Quantifier Elimination (SOQE), the problem of finding a logically equivalent first-order formula $\psi$ for a given second-order formula $\exists X \phi$ (where $\phi$ is first-order). While SOQE is undecidable in general, practical algorithms exist for specific subclasses.

The authors introduce a more general problem called Witnessed Second-Order Quantifier Elimination (WSOQE). Instead of just finding an equivalent first-order formula, the goal is to find a witness: a tuple of first-order predicates $\alpha$ such that:
$\exists X \phi \equiv \phi[X \leftarrow \alpha]$
This means the second-order formula is equivalent to the first-order formula obtained by substituting the predicate variables $X$ with specific first-order definitions $\alpha$ .

Significance of WSOQE:

It bridges the gap between SOQE and Formula Equations (FEQ) (finding $\alpha$ such that $\models \phi[X \leftarrow \alpha]$ ).
It is crucial for applications in knowledge representation (forgetting/projection), modal correspondence theory, and program verification (finding loop invariants).
Unlike standard SOQE, which only produces the result, WSOQE provides the definition of the eliminated predicates, preserving the structure of the knowledge base.

2. Methodology: The WSCAN Algorithm

The authors propose WSCAN, an extension of the existing SCAN algorithm (a saturation-based theorem prover for SOQE). The core methodology involves two main phases:

A. The SCAN Derivation

The algorithm operates on clause sets. It transforms the input formula into clausal normal form and performs a saturation process using a specific inference calculus $\mathcal{I}$ :

Constraint Resolution & Factoring: Instead of standard unification, these rules introduce inequality constraints (e.g., $t \not\simeq t'$ ) between terms.
Constraint Elimination: Unifies terms to remove constraints.
Deletion Rules:
- Extended Purity Deletion: Removes clauses containing $X$ if $X$ appears only with one polarity (all positive or all negative).
- Purified Clause Deletion: Removes a clause $P$ containing $X$ if "sufficiently many" inferences have been performed such that the remaining clause set logically entails the resolution closure of $P$ . This is formalized via a forward redundancy criterion involving variable elimination and subsumption.

The process continues until all $X$ -literals are eliminated, resulting in a first-order clause set $N^*$ equivalent to $\exists X N$ .

B. Witness Construction (Bottom-Up)

The novel contribution is the extraction of a witness $\sigma$ from the derivation history. The algorithm constructs the witness backwards (from the final state to the initial state):

Base Case: If the final clause set $N_m$ contains no $X$ , the identity substitution is a witness.
Inductive Step: For each derivation step $S_i$ $S_{i}$ transforming $N_{i-1}$ $N_{i - 1}$ to $N_i$ $N_{i}$ , the algorithm computes a substitution $\tau_{S_i}$ $τ_{S_{i}}$ such that if $\sigma_i$ $σ_{i}$ is a witness for $N_i$ $N_{i}$ , then $\tau_{S_i}\sigma_i$ $τ_{S_{i}} σ_{i}$ is a witness for $N_{i-1}$ $N_{i - 1}$ .
- For standard inference steps (Resolution, Factoring, etc.), $\tau$ is the identity.
- For Extended Purity Deletion, $\tau$ sets $X$ to $\top$ or $\bot$ depending on polarity.
- For Purified Clause Deletion (the complex case), the algorithm constructs a witness based on the local resolution closure of the deleted clause.

C. Handling Infinite Witnesses

The resolution closure used for purified clauses can be infinite, leading to infinite witnesses (expressed as infinite conjunctions). The paper introduces two solutions:

Fixpoint Witnesses: The infinite witness is expressed as a greatest fixpoint ($gfp$) in fixpoint logic. This provides a finite representation of the potentially infinite definition.
First-Order Witnesses (Acyclic Condition): The authors define a condition called $k$ -acyclically purified. If the "purification subsumption graph" associated with a deletion step is acyclic, the witness can be computed as a finite, first-order predicate using a bounded iteration of the resolution closure.

3. Key Contributions

WSCAN Algorithm: A complete method to compute witnesses for SOQE on clause sets, extending the SCAN algorithm.
Correctness Proofs:
- Proof that the constructed substitution $\sigma$ is a valid witness ( $\exists X N \equiv N\sigma$ ).
- A new correctness proof for the original SCAN algorithm derived from the witness construction logic.
First-Order Witness Guarantee: Identification of the acyclic purification condition, which guarantees that the resulting witness is a first-order formula (avoiding infinite or fixpoint expressions).
Extension of Ackermann's Lemma: The authors prove that their method subsumes Ackermann's Lemma (a classic method for SOQE) and extends it to cases where the predicate appears with mixed polarity.
Handling Background Theories: The method is extended to handle equality reasoning (via paramodulation) and first-order background theories, allowing it to solve graph reachability problems and other constrained Horn clause problems.
Prototype Implementation: A prototype implementation in the GAPT (General Architecture for Proof Theory) software package (version 2.19.0).

4. Results and Evaluation

Implementation: The prototype was tested on 44 examples (from literature and custom).
Performance:
- SCAN derivations were found for 90.9% of examples (40/44) within a 10-second timeout.
- Witness computation was extremely fast (average 0.619 ms) compared to finding the derivation (average 375 ms).
- Witness sizes were generally small (average 6.9 symbols).
Capabilities: The system successfully computed first-order witnesses for derivations that previously yielded infinite witnesses or required fixpoint logic, specifically in cases involving acyclic purification graphs.
Limitations:
- The method requires the input to be a clause set (universally quantified domain variables).
- It cannot handle cases where Skolemization is required and cannot be reversed (e.g., $\exists X \exists u \exists v (X(u) \land \neg X(v))$ ), as the resulting witness would contain Skolem constants not present in the original language.
- The search space for derivations can be large; the current implementation uses backtracking but is not optimized for massive clause sets.

5. Significance

This work is significant because it transforms the SCAN algorithm from a tool that merely eliminates quantifiers into one that synthesizes the definitions of the eliminated predicates.

Theoretical Bridge: It unifies the fields of Second-Order Quantifier Elimination (SOQE) and Formula Equations (FEQ), showing they are two sides of the same coin.
Practical Application: By providing explicit first-order definitions (witnesses), the method is directly applicable to:
- Knowledge Representation: Creating uniform interpolants and forgetting predicates while retaining the logical structure.
- Verification: Automatically generating loop invariants for program verification (solving constrained Horn clauses).
- Modal Logic: Computing correspondence axioms for modal logics.

The paper establishes that for a broad class of derivations (those with acyclic purification graphs), the complex second-order problem can be reduced to finding a finite, first-order witness, offering a powerful new tool for automated reasoning.