Introduction
Interaction Grammars (IG) represent a unique approach to linguistic modeling, utilizing a model-theoretic framework where sentence structures are derived through the resolution of "polarities"—a concept analogous to chemical valencies. While traditionally parsed using constraint-satisfaction or graph-rewriting techniques, these methods often lack the transparency required for rigorous complexity analysis and optimization. This paper presents a formal deductive parsing algorithm for IG, adapting the classic Earley framework to provide a rule-based foundation for this formalism.
The Interaction Grammar Formalism
At the heart of IG are Polarized Tree Descriptions (PTDs). Unlike the rigid rules of Context-Free Grammars (CFGs), IGs use Directed Acyclic Graphs (DAGs) to describe tree fragments. These fragments are characterized by dominance and precedence relations, with nodes carrying polarities (positive, negative, neutral, or virtual). Parsing in this context is a process of "merging" these fragments—a process called superposition—until all polarities are balanced or "saturated," resulting in a valid syntactic tree.
A Deductive Approach to Parsing
The primary contribution of this work is the mapping of the model-theoretic IG constraints into a deductive system. In this framework, the parser’s state is represented by "items" that track the progress of the parse. Given the complexity of IGs, these items are significantly more sophisticated than those in standard Earley parsing. Each item must manage three distinct sets of nodes to maintain the integrity of the parse:
- Available (D): Nodes from the lexicon ready to be used.
- Obligatory (O): Constrained nodes that must be incorporated into a specific sub-parse.
- Used (U): Nodes already integrated into the structure.
The algorithm proceeds through Axiom, Prediction, Scan, and Completion steps. Notably, the Prediction step is decomposed into three distinct phases to handle the initialization of sub-parses and the selection of antecedents from the grammar while ensuring the resulting node sets remain saturated.
Complexity and Non-Determinism
By formalizing the parsing process, the author identifies the specific sources of computational difficulty within IG. While sentence traversal is relatively straightforward, the inherent "hardness" of the process arises from two areas: lexical selection (choosing which tree fragments to use) and the partitioning of daughter nodes during the prediction phase.
The paper acknowledges that IG parsing is NP-hard. The deductive rules make this complexity explicit, showing that the number of ways to partition nodes and choose antecedents can grow exponentially without further constraints. This transparency is a significant step forward from previous "black box" constraint-solving approaches.
Conclusion and Future Directions
This deductive algorithm bridges the gap between model-theoretic linguistics and algorithmic parsing. While the current model omits polarized feature structures to maintain clarity, it establishes the necessary invariants to ensure the construction of valid syntactic trees.
Future work will focus on mitigating the NP-hardness of the system. Proposed strategies include "lazy" node partitioning (similar to techniques used in pomset-CFGs), restricting the degree of superposition allowed, and introducing algorithmic approximations to enhance real-world performance. By moving toward a structured, rule-based foundation, Interaction Grammars become more accessible to standard parsing optimization techniques.
Summary updated