Alexandra Butoi
2023
Convergence and Diversity in the Control Hierarchy
Alexandra Butoi

Ryan Cotterell

David Chiang
Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Weir has defined a hierarchy of language classes whose second member (L2) is generated by treeadjoining grammars (TAG), linear indexed grammars (LIG), combinatory categorial grammars, and head grammars. The hierarchy is obtained using the mechanism of control, and L2 is obtained using a contextfree grammar (CFG) whose derivations are controlled by another CFG. We adapt Weir’s definition of a controllable CFG (called a labeled distinguished CFG) to give a definition of controllable pushdown automata (PDAs), called labeled distinguished PDAs. This yields three new characterizations of L2 as the class of languages generated by PDAs controlling PDAs, PDAs controlling CFGs, and CFGs controlling PDAs. We show that these four formalisms are not only weakly equivalent but equivalent in a stricter sense that we call dweak equivalence. Furthermore, using an even stricter notion of equivalence called dstrong equivalence, we make precise the intuition that a CFG controlling a CFG is a TAG, a PDA controlling a PDA is an embedded PDA, and a PDA controlling a CFG is a LIG. The fourth member of this family, a CFG controlling a PDA, does not correspond to any kind of automaton we know of, so we invent one and call it a Pushdown Adjoining Automaton (PAA).
2022
Algorithms for Weighted Pushdown Automata
Alexandra Butoi

Brian DuSell

Tim Vieira

Ryan Cotterell

David Chiang
Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing
Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntaxbased statistical machine translation and transitionbased dependency parsing. As most existing dynamic programming algorithms are designed for contextfree grammars (CFGs), algorithms for PDAs often resort to a PDAtoCFG conversion. In this paper, we develop novel algorithms that operate directly on WPDAs. Our algorithms are inspired by Lang’s algorithm, but use a more general definition of pushdown automaton and either reduce the space requirements by a factor of Gamma (the size of the stack alphabet) or reduce the runtime by a factor of more than Q (the number of states). When run on the same class of PDAs as Lang’s algorithm, our algorithm is both more spaceefficient by a factor of Gamma and more timeefficient by a factor of Q x Gamma.
Search