Abstract
In the mid-1970s, the field of Natural Language Processing (NLP) was characterized by a perceived architectural divide between "meaning-first" production systems and "syntax-heavy" transition networks. This paper presents a comparative analysis of two iconic parsers from that era: Riesbeck’s Conceptual Dependency parser and the Norman/Rumelhart (LNR) parser. By re-implementing both systems within a unified computational framework—Kaplan’s General Syntactic Processor (GSP)—this study demonstrates that the systems are functionally isomorphic. The primary distinction between them lies not in their underlying semantic theories, but in their computational strategies for managing ambiguity and backtracking.
Introduction
During the formative years of computational linguistics, two distinct philosophies emerged for mapping natural language to internal representations. On one side, Riesbeck’s parser (associated with Roger Schank’s theory of Conceptual Dependency) utilized a production system of if-then rules to map sentences directly into conceptual primitives. On the other, the LNR parser utilized an Augmented Transition Network (ATN) to navigate semantic networks.
To contemporary observers, these systems appeared fundamentally different: Riesbeck’s approach seemed bottom-up and driven by semantic expectations, while LNR appeared top-down and more reliant on grammatical structure. Marc Eisenstadt’s work addresses a central question in the history of AI: Are these systems truly distinct, or are they merely different terminological expressions of the same underlying process?
Methodology: The GSP Framework
To facilitate a direct comparison, Eisenstadt employed Kaplan’s General Syntactic Processor (GSP) as a "lingua franca." GSP is a generalized formalism capable of representing both production systems and ATNs, providing a neutral ground for architectural evaluation.
By re-implementing versions of both parsers within GSP, the author was able to:
- Map Riesbeck’s "packets of production rules" onto GSP "grammar states."
- Map LNR’s "lexical flags" (indicators within the dictionary) onto GSP "augmented tests."
- Compare the step-by-step execution flow of each system as they processed new words and constructed internal representations.
The Isomorphism of Expectations
The analysis reveals that the core mechanisms of both parsers are structurally identical. In Riesbeck’s system, the verb triggers "packets" of rules that wait for specific noun types to fill conceptual slots. In the LNR system, "lexical flags" perform an identical function. Both systems use the verb to establish a set of expectations for subsequent input; they simply utilize different data structures to store and manage those expectations. This finding suggests that the choice between "Conceptual Dependency" and "Active Semantic Networks" does not inherently dictate the architecture of the parser itself.
"Safe" vs. "Risky" Processing
The most significant divergence identified was computational rather than conceptual. The difference lies in how each system handles the search space of possible interpretations:
- Riesbeck’s Parser ("Safe"): This system utilizes bottom-up interrupts to initiate operations only when specific conditions are met. By delaying commitment until a structure is certain, it effectively avoids the need for expensive backtracking.
- LNR’s Parser ("Risky"): This system performs top-down operations, essentially "guessing" a structure and then backtracking to a previous state if the path leads to a dead end.
Eisenstadt demonstrates that Riesbeck’s production system is essentially a more efficient implementation of an ATN, using lookahead and interrupts to prune the search space before errors occur.
The Red Herring of Semantic Decomposition
A common belief in the 1970s was that Riesbeck’s parser was superior because it performed "instantaneous" semantic decomposition—breaking a verb like "give" into its conceptual primitives (e.g., ATRANS) immediately upon encounter. Eisenstadt proves that the timing of this decomposition is independent of the parsing mechanism. One could just as easily perform decomposition at the end of a parse or at the beginning, regardless of whether one uses a production system or an ATN.
Conclusion
The study successfully unifies two seemingly disparate approaches to NLP. By identifying that the primary difference is the "interrupt" mechanism used to manage ambiguity, the author suggests that LNR-style parsers could be optimized with Riesbeck-style efficiency through better compiler design. This work points toward a hybrid architectural model that combines the structural clarity of transition networks with the computational efficiency of bottom-up, interrupt-driven processing.
Summary updated