Path Resolution with Link Deletion

Neil V. Murray, Erik Rosenthal

Neil V. Murray and Erik Rosenthal present Path Resolution, a hybrid inference rule for automated theorem proving that bridges the gap between traditional resolution and Prawitz analysis. By representing logical formulas as "semantic graphs," the authors provide a framework that operates on formulas in Negation Normal Form (NNF), avoiding the computational overhead and literal duplication often associated with converting formulas to Conjunctive Normal Form (CNF).

The Problem: CNF and Search Space Explosion

In automated deduction, researchers have historically faced a trade-off between Prawitz analysis and resolution. Prawitz analysis searches for contradictions without inferring new formulas, avoiding redundant data but failing to store intermediate progress. Resolution stores progress by generating resolvents but frequently leads to an exponential explosion of the search space.

Furthermore, most systems rely on Conjunctive Normal Form (CNF). Converting complex formulas into CNF can cause a massive increase in the number of literals, making the subsequent search for a proof significantly harder. Murray and Rosenthal aim to retain the strengths of both methods while working on the more flexible Negation Normal Form (NNF).

Semantic Graphs and NNF

The authors build their system on the foundation of semantic graphs. Instead of sets of clauses, formulas are represented as graphs where nodes (literals) are connected by c-arcs (conjunctions) and d-arcs (disjunctions). This allows the structure of the original formula to be preserved both visually and computationally.

Basic semantic graph representation showing nodes connected by arcs.

By working directly on NNF, the authors avoid the "literal explosion" inherent in normalization. The meaning of a formula is defined through its paths: a formula is satisfiable if there is a "c-path" (a path of conjunctions) where all literals can be true simultaneously. A contradiction exists if every c-path contains a complementary pair of literals, known as a link.

The Path Resolution Inference Rule

Path resolution is the core inference rule of this framework. It identifies "chains"—sets of complementary literal pairs (links) within the graph. If a subgraph is "spanned" by a chain (meaning every path through it contains a link), it represents a contradiction. Path resolution allows the prover to analyze a subgraph and generate a "path resolvent" relative to the rest of the graph.

An illustration of a path resolution step, showing the transformation of subgraphs during inference.

This rule acts as a "super-rule," generalizing hyper-resolution, clash-resolution, and NC-resolution into a single framework. It effectively allows Prawitz-style analysis to be performed incrementally, saving partial contradictions as the search progresses.

The paper also introduces Link Deletion strategies. Links represent potential resolution steps; deleting a link after it has been "activated" (used in an inference) is a powerful way to prune the search space. The authors formally prove that path resolution is sound and identify specific classes of resolution chains where links can be deleted without losing the "spanning property" required to find a proof.

In a standard benchmark case study from Chang and Lee (1973), path resolution required only 2 steps to reach a contradiction, whereas a standard binary resolution refutation for the same problem required 8 steps.

Conclusion

While path resolution reduces the number of inference steps and avoids CNF overhead, the authors acknowledge that finding the appropriate resolution chain within a complex graph remains a difficult search problem. Future work is needed to evaluate the implementation's performance on massive, real-world logic problems compared to modern SAT/SMT solvers and to provide full completeness proofs for all deletion strategies.

Summary updated

BibTeX
@inproceedings{murray1985path,
  author = {Neil V. Murray and Erik Rosenthal},
  title = {{Path Resolution with Link Deletion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure