💻 computer science

Anti-Unification Completeness Analysis in PVS

This paper formally establishes the completeness of a rule-based syntactic anti-unification algorithm within the Prototype Verification System (PVS), highlighting key differences between anti-unification and unification formalizations.

Original authors: Mauricio Ayala-Rincón (Universidade Federal de Goiás), Thaynara Arielly de Lima (Universidade Federal de Goiás), Maria Júlia Dias Lima (Universidade de Brasília), Temur Kutsia (RISC/Johannes Kepler Un

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mauricio Ayala-Rincón (Universidade Federal de Goiás), Thaynara Arielly de Lima (Universidade Federal de Goiás), Maria Júlia Dias Lima (Universidade de Brasília), Temur Kutsia (RISC/Johannes Kepler Universität), Marcos Mercandeli-Rodrigues (Universidade de Brasília)

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 two very different Lego castles. One is a tiny, simple tower, and the other is a massive, complex fortress with secret passages. Now, imagine you want to build a "master blueprint" that captures the essence of both castles. You want to find the parts they share (like "has a door" or "has a roof") and turn the unique, confusing bits into generic placeholders (like "a block of some color"). This process of finding the common ground while hiding the differences is called anti-unification.

For decades, computer scientists have used this trick to fix bugs, find copied code, and even turn slow software into fast, parallel software. But there was a catch: while we had a recipe (an algorithm) to build these blueprints, we didn't have a mathematically airtight guarantee that the recipe always worked perfectly for every possible pair of castles. We knew it didn't crash (it was "sound"), but we hadn't proven it found the best possible blueprint every time (it was "complete").

This paper is the story of a team of researchers who finally built that missing guarantee using a digital proof-checker called PVS.

The Puzzle of the "Solved" Pieces

To understand why this was so hard, you have to look at how the algorithm works. It breaks the two castles down piece by piece.

The Easy Part: If it sees two identical bricks, it says, "Got it!" and moves on.
The Tricky Part: If it sees two different bricks (say, a red one and a blue one), it doesn't give up like it would in a normal matching game. Instead, it says, "Ah, these are different! I'll remember this difference and keep looking for other red-vs-blue mismatches elsewhere."

In a normal matching game (called "unification"), finding a difference means you lose immediately. But in anti-unification, finding a difference is actually the goal. The algorithm has to keep a running diary of every difference it finds.

The researchers discovered that proving the algorithm works for the "easy" parts was surprisingly difficult. In fact, when they looked at their previous work, 91.10% of the effort spent proving the algorithm was correct went into just two specific cases: handling "solved" problems (where the algorithm spots a difference) and "syntactic" problems (where the pieces are identical). It sounds simple, but proving that the algorithm correctly records these differences without getting confused required a massive amount of rigorous checking.

The "History Book" of the Algorithm

The main breakthrough in this paper is realizing that to prove the algorithm finds the best blueprint, you can't just look at the current step. You have to look at the entire history of the computation.

The authors introduced a new way of thinking about the algorithm's "memory." They defined a "Total Generalizer"—a fancy term for a master blueprint that accounts for:

The pieces still waiting to be checked.
The pieces already checked and marked as "different."
The "substitution" (the list of rules) the algorithm is building as it goes.

They proved several "invariance properties." Think of these as rules that say, "No matter how many steps the algorithm takes, the total list of differences it has found so far never disappears or changes its meaning." They showed that even as the algorithm breaks a big problem into tiny sub-problems, the "story" of the original problem remains intact, just like a jigsaw puzzle that stays the same picture even when you break it into smaller pieces and shuffle them around.

The "Restricted" Blueprint

Here is the clever twist. To make the proof work, the authors had to invent a special kind of blueprint called a "Restricted Total Generalizer."

Imagine you are trying to write a recipe. If you use ingredients that are already in the kitchen (variables that the algorithm is currently using), you might accidentally change the recipe while you're writing it. So, the authors said, "Let's only use fresh, unused ingredients for our proof." They proved that if you can find a blueprint using these "fresh" ingredients, you can always translate it back to a normal blueprint.

By restricting the blueprint to these "fresh" ingredients, they were able to prove Theorem 20: The algorithm's final result is always at least as specific as any other possible blueprint you could come up with. In other words, the algorithm never misses a better solution.

What This Means (and What It Doesn't)

The paper proves (not just suggests) that the rule-based algorithm for syntactic anti-unification is complete. This means it is mathematically guaranteed to find the least general generalizer (the most precise common blueprint) for any two terms.

However, the paper is very careful about what it doesn't do yet:

It does not provide the final, machine-checked code that you can run right now. The authors state that the formalization of the new definitions and lemmas is "work in progress."
It does not claim to have solved anti-unification for all types of math (like those involving commutativity or associativity). It focuses strictly on "syntactic" anti-unification (the standard kind).
It does not claim that the algorithm is fast or efficient in terms of speed; it only proves that the logic is correct and complete.

The Bottom Line

This paper is a rigorous, step-by-step dissection of a computer algorithm. The authors didn't just say, "It works." They built a digital fortress of logic, checking every single step, especially the boring but critical parts where the algorithm spots differences. They showed that by keeping a perfect "history book" of the computation and using a clever "restricted" way of thinking about solutions, they can guarantee that the algorithm always finds the right answer.

Now that the math is proven, the door is open for the next step: extracting "certified executable code." This means that in the future, we might be able to take this algorithm and turn it into software that is guaranteed by math to never make a mistake in finding common patterns in code or chemical compounds. But for now, the victory is in the proof itself: the mystery of why it works has finally been solved.

Technical Summary: Anti-Unification Completeness Analysis in PVS

Problem Statement
This paper addresses the formal verification of the completeness of a rule-based algorithm for syntactic anti-unification within the Prototype Verification System (PVS). While previous work by the authors [9] successfully formalized and mechanically verified the termination and soundness of this algorithm, the proof of completeness remained incomplete. The paper highlights a significant disparity between the formalization of unification and anti-unification: in unification, "solved" problems (terms with different head symbols) result in failure, and syntactically equal problems are trivially resolved. In contrast, anti-unification never fails; "solved" problems indicate structural differences that must be recorded, and syntactically equal problems require the algorithm to detect and record regularities (repetitions) rather than terminating immediately. The authors note that over 90% of the effort in the previous soundness verification was devoted to these specific cases (solved and syntactic rules), suggesting that a similar, if not greater, level of rigor is required for completeness.

Methodology
The authors employ a constructive, inductive approach to prove completeness, avoiding non-constructive arguments based on the unitary type of syntactic anti-unification. The methodology relies on the existing PVS formalization of the algorithm, which operates on valid configurations consisting of unsolved problems ( $C_{Uns}$ ), solved problems ( $C_{Sol}$ ), and a computed substitution ( $C_{Sub}$ ).

To bridge the gap between soundness and completeness, the paper introduces several new theoretical constructs and preservation properties:

New Invariants: The authors define "protected variables" and "lateral substitutions" to track the history of the computation. Crucially, they establish the Problem Invariance Lemma (Lemma 7), which proves that the original anti-unification problem is preserved throughout the derivation via the composition of computed and lateral substitutions.
Extended and Total Sets of AUTs: To handle the reconstruction of the original problem from its decomposed parts, the authors define the "extended set of AUTs" ( $C_{Ext}$ ) and the "total set of AUTs" ( $C_{Tot}$ ). They prove that these sets are preserved or expanded monotonically during the derivation.
Restricted Total Generalizers: A central contribution is the introduction of a "restricted total generalizer" (Definition 19). This notion restricts the range of the generalizer to avoid variables used by the algorithm (labels and protected variables). The authors prove that if a generalizer exists, a restricted one exists that is equivalent on the relevant labels. This restriction is essential for the inductive step, allowing the construction of a generalizer for the next configuration state without conflicting with the algorithm's internal variables.

The proof proceeds by induction on the number of reduction steps from an initial configuration to a final configuration. The authors analyze the inference rules (Decompose-Function, Decompose-Pair, Solve-Repeated, Solve-Non-Repeated, and Syntactic) separately, demonstrating how the restricted generalizer can be constructed or preserved at each step.

Key Contributions

Formal Completeness Proof: The paper provides the first constructive, mechanically verifiable proof of completeness for the standard syntactic anti-unification algorithm in PVS.
Refined Generalizer Notions: The authors introduce the concepts of "total generalizers" and "restricted total generalizers," which are necessary to handle the complexity of tracking problem history and variable interactions in anti-unification, a complexity absent in standard unification proofs.
Preservation Properties: The paper establishes a suite of lemmas (Preservation of Labels, Invariance of Protected Variables, Problem Invariance, Preservation of Classification) that rigorously describe how the state of the computation evolves while maintaining the integrity of the original problem.
Differentiation from Unification: The work explicitly details why the formalization of anti-unification is more complex than unification, specifically regarding the handling of solved and syntactic subproblems where the algorithm must record differences rather than fail or terminate trivially.

Results
The primary result is Theorem 20 (Strong Completeness for Restricted Total Generalizers), which states that for any valid configuration reachable from an initial state, any restricted total generalizer is more general than the computed substitution of the final configuration. From this, Corollary 21 (Strong Completeness) is derived, establishing that the algorithm is complete with respect to arbitrary total generalizers. This confirms that the algorithm computes the least general generalizer (up to renaming) for any pair of terms.

Significance
The paper claims that completing the formal certificate for this algorithm is of "utmost importance" because it enables the extraction of certified executable code for a sound and complete anti-unification algorithm. This addresses a gap in the field where practical applications of anti-unification (such as code clone detection, parallelization, and software repair) have outpaced the development of formal, mechanically verified certificates in proof assistants. By providing a rigorous foundation for completeness, the work balances theoretical development with practical application, offering a verified basis for future extensions to anti-unification modulo algebraic properties (e.g., associativity, commutativity). The authors emphasize that the complexity of this mechanization lies in the precise recording of the decomposition history and the preservation of invariants, which distinguishes it from simpler unification formalizations.

The Puzzle of the "Solved" Pieces

The "History Book" of the Algorithm

The "Restricted" Blueprint

What This Means (and What It Doesn't)

The Bottom Line

More like this