Introduction
Published in the late 1980s, this research represents a significant milestone in computational linguistics by bridging logic programming with knowledge representation. It introduces Inheritance Grammar (IG), a formalism that merges the logic-based parsing of Definite Clause Grammars (DCG) with taxonomic inheritance. By replacing standard logic terms with hierarchical $\psi$-terms, the system enables sophisticated semantic reasoning—such as recognizing that a "boy" is both a "child" and a "male"—directly during the unification process.
The Challenge: Flat Atoms vs. Complex Features
In the 1980s, linguistic description was divided between two paradigms. Logic Grammars (like DCGs) were powerful for parsing but treated symbols as "flat" atoms; to a DCG, the symbols boy and man are as distinct as boy and bicycle, with no inherent representation of their shared human status. Conversely, Feature Structures (like PATR-II) handled complex attributes (number, person, gender) effectively but lacked a formal mechanism for "IS-A" hierarchies or taxonomies.
Harry Porter III addressed this by integrating Hassan Ait-Kaci’s work on $\psi$-terms into a grammar formalism. The objective was a system where the parser evaluates how symbols relate within a conceptual hierarchy rather than just checking for identity.
Methodology: $\psi$-terms and Lattices
The core innovation of Inheritance Grammar is the replacement of first-order logic terms with $\psi$-terms.
- The Signature and Lattice: The grammar writer defines a "signature"—a set of symbols ordered by an "IS-A" relationship (e.g.,
girl < child). The system automatically embeds these into a mathematical lattice.
- $\psi$-terms as Data Structures: Unlike standard terms, $\psi$-terms are rooted, possibly cyclic, directed graphs. Each node is a symbol from the hierarchy, and edges are labeled features (attributes).
- Unification as GLB: In standard logic, unification is binary. In IG, unification calculates the Greatest Lower Bound (GLB) in the lattice. Unifying
humanwithfeminineObjectresults in the more specific categoryhumanFemale. - Formalism: IG looks like a standard DCG but utilizes these complex $\psi$-terms as arguments, supporting multiple inheritance where a concept inherits properties from several parent categories simultaneously.
Key Insights: Semantic Filtering and Cyclicity
The use of a taxonomic hierarchy allows for semantic filtering during the parsing process. The grammar can reject nonsensical sentences early; for instance, if a verb requires a vpModifier but receives a relativeClause (an npModifier), unification fails based on the hierarchy.
Furthermore, $\psi$-terms naturally handle coreference through cyclicity. If a variable $X$ represents both the subject of a sentence and the subject of a nested relative clause, the system treats them as the same node in a graph, allowing for recursive definitions.
The system also benefits from a separation of concerns: the taxonomic hierarchy is defined independently of the grammar rules. This allows developers to update world knowledge (the hierarchy) without modifying linguistic rules (the grammar).
Results and Implementation
The author demonstrated that Inheritance Grammar is a proper superset of Definite Clause Grammar. The system was implemented in Smalltalk on a Tektronix 4406 workstation, featuring an "ordering package" for dynamic lattice construction and an incremental compiler. It successfully resolved multiple inheritance cases, such as a girl satisfying both human and feminineObject constraints without manual intervention.
Limitations and Future Directions
The initial implementation relied on top-down evaluation, which, like standard Prolog, is susceptible to infinite loops with left-recursive rules. Additionally, the computational cost of calculating GLBs in complex lattices during unification could be significant for large taxonomies. Future work suggested moving toward more robust algorithms like Earley Deduction or Extension Tables to handle a wider variety of grammar types.
This paper laid the groundwork for modern Natural Language Understanding (NLU) systems that manage structured data and constraints through unification-based grammar.
Summary updated