A tabular interpretation of bottom-up automata for TAG

Éric Villemonte de la Clergerie, Miguel Angel Alonso Pardo, David Cabrero Souto1998 · OpenReview

Abstract

Tree Adjoining Grammars (TAGs) offer the expressive power necessary to model complex natural language phenomena, such as long-distance dependencies, which exceed the capabilities of Context-Free Grammars (CFGs). However, this increased power comes with higher computational costs. This paper introduces a specialized Bottom-up 2-Stack Automaton (BU 2-SA) and a corresponding tabular interpretation. By leveraging dynamic programming, the proposed approach achieves an efficient $O(n^6)$ time complexity and an optimized $O(n^4)$ space complexity, providing a robust framework for TAG parsing.

Introduction

In computational linguistics, while CFGs are foundational, they often fail to capture the full structural complexity of human language. Tree Adjoining Grammars (TAGs) were developed to address these limitations by allowing the "adjunction" of auxiliary trees into elementary trees. Parsing TAGs typically requires more sophisticated automata than the push-down models used for CFGs.

Researchers frequently employ 2-Stack Automata (2-SA), which utilize a Master Stack (MS) for tree traversal and an Auxiliary Stack (AS) to manage adjunctions. To prevent the exponential computational explosion inherent in non-deterministic parsing, tabulation (dynamic programming) is essential. While top-down tabular parsers are well-documented, this work focuses on a systematic bottom-up strategy, which recognizes structures only after their components are fully processed.

The Bottom-Up 2-Stack Automaton (BU 2-SA)

The authors propose the Bottom-up 2-Stack Automaton (BU 2-SA), a restricted version of the more general Strongly-driven 2-Stack Automaton (SD 2-SA). The core logic involves two stacks:

  1. Master Stack (MS): Drives the primary tree traversal.
  2. Auxiliary Stack (AS): Handles bookkeeping for adjunction operations.

A defining characteristic of the BU 2-SA is the Bottom-Up Constraint: the Auxiliary Stack must remain empty during the "write" mode. This ensures that an adjunction is only acknowledged once a candidate auxiliary tree has been completely traversed.

Comparison of stack behavior between standard 2-SA and BU 2-SA. The BU 2-SA maintains an empty Auxiliary Stack during the write phase.

Tabular Interpretation and Complexity

To implement an efficient parser, the authors define a tabular framework that stores intermediate results in a table, avoiding redundant computations. The tabulation strategy utilizes two primary data structures, or "items":

  • buCF (Bottom-up Context-Free): Used for standard tree traversals.
  • buXCF (Bottom-up Escaped Context-Free): Specifically designed to handle "escaped" derivations that occur during the adjunction process.

The transitions between these items are formally defined through rules such as CALL, RET, ACALL, and ARET. This mapping allows the abstract 2-stack logic to be executed as an Earley-like parsing algorithm.

Tabular interpretation of transitions in the BU 2-SA model, illustrating the relationship between Master Stack (MS) and Auxiliary Stack (AS) states.

By optimizing the combination of these items, the algorithm achieves a time complexity of $O(n^6)$ and a space complexity of $O(n^4)$. This reduction in space complexity from the $O(n^5)$ found in some other models is a significant result of the bottom-up approach, which requires less state information to be stored during the parsing process.

Key Insights and Results

The BU 2-SA model provides a clean separation of concerns by delegating tree traversal and adjunction tracking to separate stacks. This modularity simplifies the systematic tabulation of the parsing process. Furthermore, the authors demonstrate that their tabular framework is general enough to be applied to other existing models, such as Linear Indexed Automata (LIA).

The primary contributions of this work include:

  • Formalization of Complexity Bounds: Establishing the $O(n^6)$ time and $O(n^4)$ space limits for the BU 2-SA.
  • Algorithmic Equivalence: Showing that the BU 2-SA is equivalent to other TAG parsing formalisms while offering a more direct path to efficient implementation.
  • Rule Set: Providing a complete set of transition rules for practical implementation.

Limitations and Future Work

One notable limitation of the bottom-up approach is its violation of the Valid Prefix Property. Unlike top-down parsers, a bottom-up parser cannot guarantee that the string processed so far is a valid prefix of a grammatical sentence until the entire process is complete. The practical impact of this on real-world Natural Language Processing remains a subject for further study. Additionally, while the theoretical complexity is promising, empirical benchmarks on large-scale linguistic corpora are needed to evaluate the algorithm's performance under real-world memory and time constraints.

Summary updated

BibTeX
@inproceedings{clergerie1998tabular,
  author = {Éric Villemonte de la Clergerie and Miguel Angel Alonso Pardo and David Cabrero Souto},
  title = {{A tabular interpretation of bottom-up automata for TAG}},
  booktitle = {TAG+},
  year = {1998},
  url = {https://openreview.net/forum?id=APG0Sw_YwJR},
}
Figure