Abstract
Thread Automata (TA) provide a generalized framework for parsing complex Mildly Context-Sensitive (MCS) grammars, such as Tree Adjoining Grammars (TAG) and Linear Context-Free Rewriting Systems (LCFRS). By managing multiple "threads" of computation that can be suspended and resumed, TA allows for a single, efficient tabular parsing algorithm that handles discontinuous structures common in natural language while maintaining polynomial-time complexity. This paper introduces the TA formalism and demonstrates its versatility across various grammatical systems.
Introduction
In computational linguistics, different grammatical formalisms—such as TAG, Multi-Component TAG (MCTAG), and LCFRS—often require distinct, specialized parsing algorithms. Éric Villemonte de la Clergerie identifies the need for a high-level, unifying automaton that can describe a wide range of parsing strategies (particularly top-down, prefix-valid ones) across these different systems. The primary challenge addressed is the handling of "discontinuous constituents"—parts of a sentence that belong together grammatically but are separated by other words, a common feature in MCS languages.
The Thread Automata Framework
The core innovation of Thread Automata is the "thread store," which replaces the traditional single stack or state. Each thread represents a line of computation tasked with recognizing a specific constituent. Only one thread is active at any given time, but the system supports complex lifecycle operations:
- PUSH/POP: A thread can initiate a sub-thread to recognize a sub-constituent and terminate it upon completion.
- SPUSH/SPOP (Suspend/Resume): This allows a thread to be suspended, returning control to its parent or a descendant. This mechanism is ideal for modeling "holes" in constituents, such as the gap in a TAG auxiliary tree.
The parser utilizes a tabular algorithm based on a Dynamic Programming (DP) interpretation, breaking derivations into "items" to avoid redundant computation.
Handling Discontinuity and Interleaving
A thread's path acts as a unique identifier, enabling the parser to track deeply nested or interleaved structures. By allowing multiple suspensions and resumptions, TA can handle complex interleaving where constituents overlap in the input string.
The complexity of parsing is driven by two parameters: $h$ (maximum suspensions per thread) and $d$ (maximum active sub-threads). Formalisms like CFG, TAG, and LCFRS can be viewed as specific configurations of these parameters within the TA framework.
Complexity and Results
The general tabular parser for TA achieves a worst-case space complexity of $O(n^{2(1+h+dh)})$ and time complexity of $O(n^{2(1+h+dh)+1})$. For standard TAG ($h=1$), the formalism is expected to reach the optimal $O(n^6)$ time complexity with refined DP interpretations. The paper also provides encoding "recipes" for tree-local MCTAG, set-local MCTAG, and ordered simple RCGs, proving the formalism's broad applicability.
Conclusion and Future Work
While TA offers a powerful unifying framework, further work is needed to refine TAG encoding for optimal complexity and to explore the full spectrum of supported languages. Future efforts will focus on implementation within the DyALog system and investigating theoretical links to other automata like Embedded Push-Down Automata.
Reference: Éric Villemonte de la Clergerie. Proceedings of the Sixth International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+6). 2002.
Summary updated