💻 computer science

Completeness of Synthesis under Realizability Assumptions using Superposition

This paper introduces a refined superposition-based calculus for synthesizing recursion-free programs that is proven to be sound and complete, guaranteeing the discovery of a computable solution whenever one exists.

Original authors: Márton Hajdu, Petra Hozzová, Laura Kovács, Eva Maria Wagner

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Márton Hajdu, Petra Hozzová, Laura Kovács, Eva Maria Wagner

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 architect (the computer) trying to build a house (a computer program) based on a very specific set of blueprints (the user's requirements). The tricky part is that the blueprints mention some magical, invisible materials (uncomputable symbols) that you are strictly forbidden from using in the actual construction. Your job is to build a house using only standard, real-world bricks (computable symbols) that still perfectly matches the blueprint's description.

This paper is about a new, smarter way for the architect to figure out how to build that house without getting stuck.

The Problem: Getting Stuck in the "Magic" Zone

In the past, architects used a method called Superposition (a fancy way of saying "systematically testing combinations of rules"). They would try to prove the house could be built by mixing and matching rules.

However, the old method had a flaw. Sometimes, the blueprint would say, "The roof must be made of Magic Dust (uncomputable), but the walls must be Bricks (computable)." The old architect would get confused. They would try to mix the Magic Dust with the Bricks, realize they couldn't use the Magic Dust, and then give up, even though a solution using only Bricks actually existed. They were stuck because they didn't know how to ignore the "Magic Dust" long enough to find the brick-only solution.

The Solution: The "SUPRA" Framework

The authors introduce a new framework called SUPRA (Superposition with Realizability Assumptions). Think of this as a new set of rules for the architect that guarantees they will find a solution if one exists.

Here is how SUPRA works, using three simple metaphors:

1. The "Heavy Bag" Rule (Ordering)

Imagine the blueprint has two types of instructions:

Heavy Instructions: "Use Magic Dust."
Light Instructions: "Use Bricks."

In the old method, the architect might try to solve the "Light" instructions first, get confused by the "Heavy" ones, and quit.
In SUPRA, the architect is forced to treat the "Heavy" instructions as if they weigh a ton. They must deal with the heavy, forbidden materials first. By tackling the "Magic Dust" rules immediately, the architect clears the path to see how to build the rest of the house using only the allowed "Bricks."

2. The "Abstracting" Trick (The Abs Rule)

Sometimes, the blueprint says, "The door handle must be made of Magic Glass," but the handle is attached to a Wooden Door (which is allowed).
The old architect would try to build the handle out of Magic Glass and fail.
The new SUPRA architect uses a trick called Abstraction. They say, "Okay, I can't use Magic Glass, so let's pretend the handle is just a 'Mystery Object' for a moment." They separate the "Magic" part from the "Wood" part. This allows them to solve the puzzle for the Wooden Door first. Once the door is built, they can figure out how to replace the "Mystery Object" with a real, allowed material that fits the same spot.

3. The "Answer Key" (Answer Clauses)

As the architect builds, they keep a running list of "Answer Keys." Every time they make a logical step, they write down: "If I do X, the answer is Y."
In the past, these keys could get messy and contradictory. SUPRA keeps these keys very organized. If the architect reaches a point where they have a complete, valid house made only of allowed materials, the "Answer Key" lights up with a green checkmark, showing the final program.

The Big Claim: "Completeness"

The most important thing this paper claims is Completeness.

In the world of math and logic, "completeness" means: "If a solution exists, we will definitely find it."

The authors prove that if there is any possible way to build the house using only allowed materials, their new SUPRA method will eventually find it. They don't just say "it usually works"; they provide a mathematical guarantee. If the blueprint is solvable, the architect will not get stuck; they will finish the job.

Summary

The Goal: Automatically write computer programs that are guaranteed to be correct, even when the requirements mention things the program can't actually use.
The Old Way: Sometimes got confused by the forbidden "magic" parts and gave up, even when a solution was possible.
The New Way (SUPRA):
1. Forces the system to deal with forbidden parts first (so they don't get in the way).
2. Uses a "pretend" trick to separate forbidden parts from allowed parts.
3. Guarantees that if a solution exists, the system will find it.

This paper is a theoretical breakthrough in automated reasoning, ensuring that our digital architects never miss a valid design just because they were distracted by the "magic" in the instructions.

Technical Summary: Completeness of Synthesis under Realizability Assumptions using Superposition

Problem Statement
The paper addresses the problem of automated program synthesis, specifically the task of deriving a recursion-free program from a first-order logical specification. The core challenge lies in the presence of "uncomputable symbols" within the specification. These symbols, which may include user-annotated predicates or Skolem functions introduced during proof search, cannot appear in the final synthesized program. The synthesized program must be constructed solely from "computable symbols" (e.g., standard arithmetic, user-defined functions) while satisfying a specification that may mix both computable and uncomputable symbols.

Previous work by Hozzová et al. [14] introduced a saturation-based framework using the superposition calculus to solve this problem. While that approach was proven sound (any derived program is correct), its completeness remained an open question. Specifically, it was unclear whether the calculus could guarantee finding a solution if one existed (realizability assumption). The paper identifies specific scenarios where the calculus of [14] fails to derive a solution even when a computable program exists, primarily due to limitations in how it handles term orderings, selection functions, and the interaction between computable and uncomputable literals.

Methodology: The SUPRA Calculus
The authors propose a refined calculus named SUPRA (Superposition with Realizability Assumptions) to address the incompleteness of the previous framework. The methodology involves three primary technical adjustments to the standard superposition-based synthesis approach:

Partitioned Orderings and Selection:
The paper introduces a "partitioned" simplification ordering. In this ordering, any ground uncomputable term is strictly greater than any ground computable term. Consequently, the selection function is constrained to always select all maximal literals in a clause. This ensures that inferences involving uncomputable literals (which are larger) are prioritized over those involving only computable literals. This prevents the calculus from getting stuck in derivations where uncomputable constraints block the resolution of computable branches.
Abstraction Rule (Abs):
To handle cases where uncomputable equations contain computable subterms that need to be resolved before the uncomputable literal can be processed, the authors introduce an auxiliary inference rule called Abs. This rule abstracts computable subterms within uncomputable literals by replacing them with fresh variables and adding disequality constraints (e.g., transforming $s[k] \approx t$ into $s[x] \approx t \land x \neq k$ ). This mechanism separates the reasoning about uncomputable symbols from computable ones, allowing the calculus to resolve uncomputable literals without violating the computability constraint of the answer term.
Refined Inference Rules:
The calculus utilizes two variants of the superposition rule:
- SupC: Introduces an ite (if-then-else) constructor in the answer term when branching on an equality literal.
- SupU: Unifies answer terms from premises directly, avoiding the addition of constraints that might lead to uncomputable conditions.
  The calculus also replaces the "computable unifiers" used in [14] with standard most general unifiers (MGUs), relying on the partitioned ordering and the Abs rule to ensure that the resulting answer terms remain computable.

Key Contributions

Identification of Incompleteness: The paper demonstrates via counter-examples (e.g., a workshop scheduling scenario and a constant manipulation scenario) that the calculus in [14] is not complete under realizability assumptions. It fails to find solutions when the selection of literals or the ordering of terms prevents necessary inferences on uncomputable symbols.
The SUPRA Framework: The authors define the SUPRA calculus, incorporating the partitioned ordering, the Abs rule, and specific selection constraints.
Soundness Proof: The paper proves that SUPRA is sound with respect to the semantics of answer clauses, ensuring that any program derived is a valid solution to the synthesis specification.
Completeness Proof: The primary theoretical contribution is the proof that SUPRA is complete under the assumption of realizability. The authors show that if a computable program satisfying the specification exists, the SUPRA calculus (when used exhaustively with the Abs rule) is guaranteed to derive a solution. The proof constructs a model for the saturated set of clauses and demonstrates that if no solution were derived, a contradiction would arise regarding the satisfiability of the negated specification.

Results and Significance
The paper establishes that program synthesis via saturation-based theorem proving can be made complete under realizability assumptions by carefully managing the interaction between computable and uncomputable symbols. The significance of this work lies in closing the theoretical gap left by previous research [14], providing a formal guarantee that the synthesis process will succeed if a solution exists within the computable signature.

The authors note that their notion of realizability applies to recursion-free programs; the construction of recursive programs requires mechanisms (like induction) not covered by the current calculus. Furthermore, the completeness result is conditional: it guarantees finding a solution if one exists, rather than proving the existence of a solution for all specifications. The work relies on standard first-order logic with equality and does not claim to solve synthesis problems involving theories that require quantifier elimination (like linear arithmetic) unless those theories are handled by the underlying prover's theory reasoning capabilities.

In summary, the paper refines the superposition calculus for synthesis by introducing a partitioned ordering and an abstraction mechanism, proving that these modifications are sufficient to ensure completeness for recursion-free program synthesis in the presence of uncomputable symbols.