Algorithms for Weighted Pushdown Automata (2022)

Abstract: Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency parsing. As most existing dynamic programming algorithms are designed for context-free grammars (CFGs), algorithms for PDAs often resort to a PDA-to-CFG 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 space-efficient by a factor of |Gamma| and more time-efficient by a factor of |Q| x |Gamma|.

## introduction weighted pushdown automata (wpdas) are widespread in natural language processing (nlp), primarily in syntactic analysis. for instance, wpdas have found use in syntax-based statistical machine translation @xcite , and many transition-based dependency parsers @xcite @xcite @xcite @xcite are special cases of wpdas. in addition, pdas have been used in computational psycholinguistics as models of human sentence processing @xcite . despite their ubiquity, there has been relatively little research on the theory of wpdas themselves. in some ways, wpdas are treated as second-class citizens compared to their equivalent cousins, weighted contextfree grammars (wcfgs), for which a variety of dynamic programming algorithms exists @xcite @xcite . to help fill this gap, this paper offers several new and improved algorithms for computing with wpdas. figure 1 gives an overview of most of our results. we start by defining a weighted version of the extended pdas of @xcite and two special cases: the standard definition @xcite , which we call topdown, and its mirror image, which we call bottomup. both top-down and bottom-up wpdas have been used in nlp. @xcite generative parser is a top-down pda as is @xcite . most transition-based dependency parsers, both arc-standard @xcite and arc-eager @xcite , are bottom-up wpdas. next, we give a normal form for wpdas analogous to chomsky normal form, and we derive new dynamic programming algorithms to compute the weight of a string under top-down and bottom-up wpdas in normal form. we are only aware of one previous recognition algorithm for pdas, that of @xcite , which we generalize to the weighted case and improve in the following ways: • on pdas more general than those lang considers, our algorithm is more space-efficient by a factor of |γ| (the stack alphabet size); • we can speed up our algorithm to be more timeefficient by a factor of more than |𝑄| (the number of states), but without the space-complexity improvement; • on the same pdas that lang considers, which we call simple, our sped-up algorithm is more efficient by a factor of |γ| in space and |𝑄| • |γ| in time. compared with the pipeline of standard procedures for converting a top-down pda to a cfg, converting to chomsky normal form, and parsing with cky, our top-down algorithm is faster by a factor of more than 𝑂 (|𝑄| 3 ). finally, we present iterative algorithms for computing the total weight of all runs of a wpda. ## normal form in this section we present a series of semanticspreserving transformations for converting an arbitrary pushdown automaton into a normal form that is analogous to chomsky normal form for contextfree grammars. this will help us obtain a fast algorithm for computing stringsums. definition 15. a bottom-up wpda is in normal form if all of its scanning transitions are 𝑘-pop, 1-push for 𝑘 ≤ 2, and all of its non-scanning transitions are 2-pop, 1-push. similarly, a top-down wpda is in normal form if all of its scanning transitions are 1-pop, 𝑘-push for 𝑘 ≤ 2, and all of its non-scanning transitions are 1-pop, 2-push. ## stringsums in bottom-up wpdas in this section, we give dynamic programming algorithms for computing the stringsum of an input string 𝒔 (with |𝒔| = 𝑛) of bottom-up wpdas in normal form. we give a basic version of the algorithm, which has the same runtime as lang's algorithm but improved space requirements, and a fast version that has the same space complexity and runs asymptotically faster. on simple pdas (for which lang's algorithm was designed), the latter version has both improved space and time complexity. ## stringsums in top-down wpdas stringsums of weighted top-down wpdas can be computed by the left/right mirror image of our bottom-up algorithm. instead of finding push computations, this algorithm finds pop computations, which decrease (rather than increase) the stack size by exactly one. definition 18 (pop computation). let p be a top-down wpda and 𝒔 ∈ σ * an input string. a pop computation of type ## allsums in bottom-up wpdas we can use a notion of push computation similar to def. 14 to derive a space-efficient algorithm for computing allsums in bottom-up wpdas. the item [ 𝑝, 𝑋, 𝑞] stands for runs from state 𝑝 to state 𝑞 that push the symbol 𝑋 on top of the stack while leaving the symbols underneath unchanged. definition 19 (push computation). let p be a bottom-up wpda. a push computation of type these items closely resemble those used for computing stringsums, but discard the two variables 𝑖, 𝑗 that we used for indexing substrings of the input, as we are interested in computing the total weight of runs that scan any string. definition 20. let π ( 𝑝, 𝑋, 𝑞) be the set containing all push computations from state 𝑝 to state 𝑞 that push 𝑋. the allsum w[ 𝑝, 𝑋, 𝑞] is defined as w[ 𝑝, 𝑋, 𝑞] = 𝝅 ∈π ( 𝑝,𝑋,𝑞) ## conclusion our study has contributed several results and algorithms whose weighted cfg analogues have long been known, but have previously been missing for weighted pdas-a normal form analogous to chomsky normal form and a stringsum algorithm analogous to weighted cky. but it has also revealed some important differences, confirming that the study of weighted pdas is of interest in its own right. most notably, we identified two different normal forms and two corresponding stringsum algorithms (and two allsum algorithms). since the only existing pda stringsum algorithm we are aware of, lang's algorithm, is better suited to bottomup pdas, whereas the more standard definition of pdas is of top-down pdas, our algorithm for top-down wpdas fills a significant gap.