Abstract
This paper presents a system that automatically designs specialized data representations for complex logic puzzles, such as those found on graduate school entrance exams. Instead of relying on slow, general-purpose theorem provers, the authors propose an approach that maps problem statements to a library of mathematical types (like sets and partitions) to generate efficient, custom-built LISP programs that solve the problem in seconds.
Problem Statement
In the late 1980s, AI research faced a significant hurdle: general-purpose theorem provers were technically "complete" but practically useless for "analytical reasoning" problems (think LSAT or GRE logic games). These solvers treated every piece of information as an abstract axiom, leading to a combinatorial explosion of possible inferences.
Humans, by contrast, solve these problems by sketching diagrams or creating mental models—specialized representations that make the "important" things explicit and constrain the search space. The authors identify a gap in AI: we know a "good" representation when we see one, but we didn't have a formal, prospective method for designing one from a raw problem statement. This paper seeks to automate that design process.
Methods
The authors treat representation design as a three-step pipeline: Representation Introduction, Dependent Representation Introduction, and Operationalization.
1. The Type Library
The core of the system is a hierarchy of mathematical concepts (e.g., set, binary-relation, equivalence-relation, partition). Each type comes with pre-defined data structures and procedures.
2. Taxonomic Classification & Revision
The system takes a predicate calculus translation of the problem and tries to "fit" its relations into the library. If a relation like married(x, y) is found to be symmetric and intransitive, the system uses Concept Revision Heuristics to transform it. For example, it might decide that "married" is better represented as a set of COUPLES.
3. Operationalization
Not every constraint fits into a neat data structure. For the "leftover" logic formulas, the system generates "demons" or procedural methods. If the problem says "siblings are symmetric," the system writes a piece of code that ensures if $A$ is added to $B$’s sibling set, $B$ is automatically added to $A$’s.
4. Code Generation
Finally, the system outputs an object-oriented LISP program tailored specifically to that one puzzle.
Datasets and Evaluation
The system was tested on a small number of verbal reasoning problems typical of graduate school admissions tests (GRE/LSAT). The primary example used throughout the paper is a family tree puzzle involving seven individuals ($M, N, O, P, Q, R, S$) and various relationships (niece, grandfather, only child, etc.).
No large-scale benchmarks are mentioned, as the focus was on the architectural feasibility of the design process.
Key Insights
- Syntax as Semantics: A "good" representation is one where the syntax of the data structure itself enforces the rules of the domain. If a "couple" is defined as a set of size two, the system literally cannot represent a three-person marriage, eliminating a whole class of impossible search paths.
- Invariants over Search: Instead of searching for a proof, the system maintains "invariants." When new information is added, the specialized behaviors of the data structures propagate the consequences immediately (e.g., identifying that two people must be the same person because they are both the "only child" of the same parent).
- The Power of Reformulation: The paper argues that the hardest part of problem-solving isn't the logic itself, but the "relabeling" of the phenomenon. Moving from the relation
married(x, y)to the objectCOUPLEis a creative leap that the system automates using mathematical heuristics.
Key Results
The authors demonstrated the system on a Symbolics 3600 (a high-end LISP machine of the era):
- Design Efficiency: It took approximately 20 minutes to derive the specialized representation and another 5 minutes to generate the LISP code.
- Execution Speed: Once the custom program was built, it solved the family tree puzzle in less than five seconds.
- Search Reduction: The resulting program was significantly more efficient than a general theorem prover because it only performed "tightly constrained local processes" rather than an exhaustive global search.
Limitations and Future Work
The authors admit their 12 revision heuristics are somewhat ad hoc and lack a rigorous mathematical underpinning. Furthermore, the current implementation is limited to "extensional sets"—problems where you are reasoning about a finite, specific group of objects. It is unclear how this would scale to infinite domains or continuous physics. Finally, the success of the approach depends entirely on the sophistication of the Type Library; if a problem requires a mathematical structure not in the library, the system fails.
Summary updated