Abstract
Nous définissons un formalisme, les grammaires rationnelles d’arbres avec traits, et une traduction des grammaires d’arbres adjoints avec traits vers ce nouveau formalisme. Cette traduction préserve les structures de dérivation de la grammaire d’origine en tenant compte de l’unification de traits. La construction peut être appliquée aux réalisateurs de surface qui se fondent sur les arbres de dérivation.
Introduction
Tree Adjoining Grammars (TAG) are a prominent formalism in computational linguistics, particularly valued for their ability to model long-distance dependencies. A TAG analysis typically yields two distinct structures: a derived tree, representing the surface syntactic structure, and a derivation tree, which records the history of tree combinations (substitution and adjunction).
In practical applications, "feature-based" TAGs (FB-TAG) are used, where nodes are decorated with feature structures (e.g., gender, number). These features must unify across the derivation. However, managing these constraints efficiently is challenging. Standard models often suffer from "delayed validation," where feature mismatches are only detected late in the generation process, leading to significant backtracking and computational inefficiency.
Methodology: Regular Tree Grammars and Left-Corner Transformation
To address these issues, the authors propose translating FB-TAGs into Regular Tree Grammars (RTG) with features. This translation maps the complex operations of TAG into a simpler, more mathematically tractable formalism.
The core innovation is the application of a left-corner transformation to the resulting RTG. While traditionally used to improve parsing efficiency, the authors demonstrate its utility in surface realization (generation). By reordering grammar rules, the system can validate feature compatibility as soon as a new branch is initiated. This "predictive generation" allows for early pruning of invalid derivation paths, mitigating the state-explosion problem often seen in large-scale grammars like SEMFRAG.
Key Insights and Results
The research highlights several critical advantages of this approach:
- Derivation Trees as Pivots: Derivation trees are argued to be superior for semantic generation tasks because they provide a primitive semantic view of the sentence structure.
- Formal Efficiency: The translation to RTG is linear in time relative to the size of the original TAG, and the transformed grammar remains manageable in size (at most doubling the number of rules).
- Improved Readability and Predictivity: The transformed rules are more intuitive. For instance, a determiner like "le" can immediately specify its requirement for a masculine singular noun, rather than verifying this constraint at the end of a long derivation chain. This framework handles both finite feature domains and infinite ones (like semantic indices).
Conclusion and Future Work
The proposed framework provides a robust method for handling unification in TAG derivation trees. While the current work focuses on derivation structures, future extensions could include full syntactic parsing by integrating word-order information. Additionally, this formalism could serve as a tool to identify if a complex TAG can be simplified into computationally cheaper classes, such as Tree Insertion Grammars.
Summary updated