A redefinition of Embedded Push-Down Automata

Miguel A. Alonso, Éric Villemonte de la Clergerie, Manuel Vilares Ferro2000 · OpenReview

Abstract

Tree Adjoining Grammars (TAGs) are essential for describing complex natural language structures, yet their corresponding automata—Embedded Push-Down Automata (EPDA)—are notoriously difficult to implement efficiently. This paper introduces a state-free definition of EPDA that simplifies the formal model, enabling polynomial-time parsing through tabulation.

Problem Statement

Standard EPDAs utilize a complex system of nested stacks. A naive execution of these machines often results in exponential time complexity, rendering them impractical for real-world natural language processing (NLP). The authors aim to redefine the EPDA to be compatible with tabulation, a dynamic programming technique that stores intermediate results to avoid redundant computations and ensures polynomial-time execution relative to input length.

Redefining the EPDA

The authors employ three primary strategies to optimize the EPDA:

  1. State Elimination: They demonstrate that finite-state control is unnecessary if the "current state" is stored directly within the top stack element. This simplifies the formal model into a tuple of terminal symbols, stack symbols, and transitions.
  2. New Transition Set: Six specific transition types are defined to handle the operations required for TAGs, particularly the "adjunction" operation.
  3. Tabulation Framework: A set of inference rules defines "items" (traces of machine configurations), classifying derivations into "Call" (top-down) and "Return" (bottom-up) types.
Table 1: Comparison of transition types between state-free EPDA and L-LIA.

As shown in Table 1, the transition set includes standard operations like SWAP, PUSH, and POP, alongside novel WRAP-A and WRAP-B operations. These "wrapping" transitions are the critical mechanism for handling TAGs; they allow the machine to insert new stacks above or below the current top stack, effectively pausing the processing of a main tree to handle an auxiliary tree (adjunction) before resuming.

Tabulation and Polynomial Complexity

The core contribution is the tabulation framework, which ensures the machine runs in polynomial time. By using inference rules, the automaton can "remember" previously explored paths, avoiding the exponential explosion of naive stack processing.

Figure 1: The call/return structure within the tabulation framework.

Figure 1 visualizes the structured navigation of these nested stack configurations. The framework distinguishes between different types of calls (ACALL, SCALL, FCALL) and returns (ARET, SRET, FRET), providing the necessary traces to maintain stack integrity during polynomial-time parsing.

Key Insights and Results

The paper establishes a direct correspondence between the redefined EPDA and Left-oriented Linear Indexed Automata (L-LIA), unifying two distinct approaches to TAG parsing. The authors successfully provided a compilation schema proving that this streamlined, state-free EPDA accepts exactly the class of Tree Adjoining Languages while maintaining polynomial complexity.

Conclusion

While the authors provide a robust solution for a significant subset of transitions, they note that the tabulation of EPDA using unrestricted PUSH and POP transitions remains a challenge. Future work involves refining these inference rules to further optimize the constant factors in polynomial time complexity.

Summary updated

BibTeX
@inproceedings{alonso2000redefinition,
  author = {Miguel A. Alonso and Éric Villemonte de la Clergerie and Manuel Vilares Ferro},
  title = {{A redefinition of Embedded Push-Down Automata}},
  booktitle = {TAG+},
  year = {2000},
  url = {https://openreview.net/forum?id=FpSRsSTBWMe},
}
Figure