Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages (2023)

Abstract: The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of a context-free grammar (CFG) or pushdown automaton (PDA) controlling another CFG or PDA. These four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA), and embedded pushdown automata (EPDA). We define semiring-weighted versions of the above two-level formalisms, and we design new algorithms for computing their stringsums (the weight of all derivations of a string) and allsums (the weight of all derivations). From these, we also immediately obtain stringsum and allsum algorithms for TAG, LIG, PAA, and EPDA. For LIG, our algorithm is more time-efficient by a factor of \mathcal{O}(n|\mathcal{N}|) (where n is the string length and |\mathcal{N}| is the size of the nonterminal set) and more space-efficient by a factor of \mathcal{O}(|\Gamma|) (where \Gamma is the size of the stack alphabet) than the algorithm of Vijay-Shanker and Weir (1989). For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of \mathcal{O}(|\Gamma|^2) and \mathcal{O}(|\Gamma|^3) , respectively. Finally, we give the first PAA stringsum and allsum algorithms.

## preliminaries let [i:j] denote the sequence of integers (i, . . . , j). if s is a string, we write |s| for the length of s, s i for the i th symbol of s, and s (i:j] for the substring s i+1 • • • s j . ## computing stringsums in this section, we give a deduction system for computing stringsums of a particular string s in cfg ▷ cfg in normal form. stringsums of a string s can be computed analogously in pda ▷ cfg, cfg ▷ pda, and pda ▷ pda; we show the deduction systems for these in app. c.2. due to d-strong equivalence, these deduction systems can also be used for spinal tag, lig, epda, and spinal paa by first converting them to their equivalent twolevel formalism. our algorithms have improved space requirements and run asymptotically faster than the best algorithms for lig and epda. moreover, it is the only stringsum algorithm for paa that we are aware of. ## computing allsums we reuse the notion of pop computation that we defined in §4.1 in order to derive a space-efficient algorithm for computing allsums of cfg ▷ cfg. allsums of pda ▷ cfg, cfg ▷ pda, and pda ▷ pda can be computed similarly (see app. d). we define a new type of pop computation that will help us compute the weight of all derivations instead of derivations of a particular string. definition 11. let g 1 be a controller wcfg and g 2 a wld-cfg, with nonterminal alphabets n 1 and n 2 , respectively. let be a symbol not occurring in the rules of a pop computation of type x [a] is a partial derivation x [a] * = ⇒ s, where @xmath0. fig. 4b shows the deduction system for computing allsums. just as for stringsums, we distinguish two types of items, those of type theorem 2. let g 1 be a controller wcfg with nonterminal alphabet n 1 and start symbol s, and g 2 a wld-cfg with nonterminal alphabet n 2 . assume that both have weights in an ω-continuous semiring (app. a.1). then the allsum of g 1 ▷ g 2 is the value of the item s [s] in the deductive system of fig. 4b . unlike for stringsums, this deduction system has cycles. the value of the goal item s [s] can be found using fixed-point iteration @xcite or the semiring generalization of newton's method @xcite . since there are various algorithms for computing item values, we don't analyze time complexity, but only space complexity. let n 1 and n 2 be the sets of nonterminals or stack symbols of the controller and the controllee, respectively. as the algorithm needs to store an item of the form for each x , @xmath1, and an item of the form x [a] for each @xmath2, it has a space complexity of o(|n 1 ||n 2 | 2 ). if we were to compute allsums in lig using an algorithm based on vijay-shanker and weir's (1989) algorithm, we would have stored o(|n 1 | 2 |n 2 | 2 ) items, therefore we have a space improvement of a factor of |n 1 |. similarly, we get a space improvement for epda of a factor of |n 1 | 2 over the allsum algorithm based on alonso et al.'s (2001) algorithm. ## conclusion our work has contributed several new results and algorithms for l 2 formalisms. we introduced semiring-weighted versions of controllable cfgs and pdas, which give rise naturally to four semiring-weighted two-level formalisms when they are controlled by semiring-weighted cfgs and pdas. we also introduced a wpda normal form that is completely analogous to the chomsky normal form for cfgs and showed that one can derive normal forms for the two-level formalisms only from the normal forms of the controller and of the controllee. these normal forms are also normal forms for tag, lig, paa, and epda, respectively, and the conversions only require conversions of the controller and the controllee. finally, we designed new stringsum and allsum algorithms for all of these formalisms, some of which are faster or more space-efficient than several existing algorithms.