ModGen: Theorem Proving by Model Generation

Sun Kim, Hantao ZhangAAAI 1994

Bridging the Gap in Automated Reasoning

In the field of automated reasoning, a significant divide exists between resolution-based provers and Constraint Satisfaction Problem (CSP) solvers. Resolution-based provers, such as OTTER, excel at general logic but often struggle with finite-domain problems, like proving commutativity in specific algebraic groups. Conversely, CSP solvers are optimized for finite domains but typically require problems to be formatted in highly restricted propositional clauses.

ModGen addresses this "sweet spot" by translating first-order logic formulas into the language of Boolean Satisfiability (SAT). By grounding complex mathematical problems into propositional logic, ModGen leverages the high performance of modern SAT solvers while maintaining the expressive power of first-order logic.

The ModGen Architecture

ModGen consists of two primary components designed to streamline the translation and solving process. The first is a Propositional Clause Generator, which transforms first-order formulas (using OTTER syntax) into propositional clauses. The second is the SATO Solver, an efficient implementation of the Davis-Putnam algorithm used to find models for these generated clauses.

The ModGen system architecture.

The core technical challenge in this architecture is avoiding "clause explosion," where the translation results in a SAT instance too large to solve. ModGen employs several optimization techniques to mitigate this:

  • Function Elimination: Soundly replacing functions with predicates.
  • Skolem Function Optimization: Preventing quadratic blow-up by eliminating existential quantifiers when they depend on all universal variables.
  • Symmetry Checking: Detecting predicate invariance to skip redundant clause generation.

Key Insights and Strategies

A critical finding in the development of ModGen is that the method of translation is as vital as the solver's efficiency. The authors highlight the difference between "Direct" and "Indirect" strategies for handling equalities. While the indirect method introduces new variables for every function instance, the direct transformation significantly reduces the number of ground clauses.

Performance comparison of Indirect vs. Direct equality handling strategies.

As shown in the Quasigroup 6 (GQ6) benchmarks, the impact is dramatic. For an order 7 problem, the Direct strategy completed the task in just 0.47 seconds, whereas the Indirect strategy required 2290.65 seconds. This demonstrates that a smart translation layer is essential for scaling theorem proving via SAT.

Experimental Results

ModGen was evaluated against classic logic benchmarks and specialized solvers like FINDER. Key performance highlights include:

  • Speed: On the "Non-Obviousness" logic puzzle, ModGen finished in 0.04 seconds, compared to OTTER's 3.8 seconds.
  • Scalability: In the N-Queens problem, ModGen outperformed FINDER for orders greater than 10, successfully calculating all 2,279,184 solutions for the 15-queen problem in approximately 2.6 hours.
  • Compatibility: By supporting OTTER syntax, ModGen serves as a drop-in tool for researchers, allowing them to pivot between resolution and model generation without reformatting their problem sets.

Limitations and Future Work

Despite its efficiency, ModGen is currently limited to problems with finite Herbrand domains and cannot handle infinite sets, such as general number theory, without manual bounding. Additionally, while ModGen is superior for finding all solutions or proving unsatisfiability, specialized local search algorithms remain faster for finding single solutions to problems like N-Queens. Future research may address the "Wos Problem"—determining the optimal criteria for choosing between predicate and function notation during problem representation.

Summary updated

BibTeX
@inproceedings{kim1994modgen,
  author = {Sun Kim and Hantao Zhang},
  title = {{ModGen: Theorem Proving by Model Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure