Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
Authors: Alexandra Butoi
Tim Vieira
Ryan Cotterell
David Chiang
Venue: EMNLP 2023 Main (2023)
Keywords: algorithms
parsing
semirings
tree adjoining grammars
linear indexed grammars
embedded pushdown automata

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.

Efficient Algorithms for Recognizing Weighted Tree-Adjoinigg Languages
Alexandra Butoi*
Tim Vieira
Ryan Cotterell' David Chiang²
EETH Zürich
UUniversity of Notre Dame
(alexandra butoi, ryan. cannccoteeeel jeattereelJ@eff.... ethz. ch
dchiang@nd. edu
tim. www.f.vviirra@aaal..... com
Abstract
WLD-CCG
The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of context-free grammar (CFG) or pushdown automaton (PDA) controlling an- other CFG PDA. These four formalisms equivalent to tree- rreeannjo grammars (TAG), linear indexed grammars (LIG), pushdown- adjoining automata (PAA), and embedded push- down automata (EPDA). We define semiring- weighted versions of the above two-level for- malisms, and we design new algorithms for computing their stringsums (the weight of all derivations a string) and allsums (the weight of all derivations). From these, we also imme- diately obtain stringsum and allsum algorithms for TAG, LIG, PAA, and EPDA. For LIG, algorithm is more time- effeceffiiennt by factor of O(][W]] (where n is string length and [W] is the size of the nonterminal set) and more space-efficient by a factor of O((1)) (where I is the size of the stack alphabet) than the algorithm of Vijay-Shanker and Weir (1989). For EPDA, our algorithm both more space- efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of O(I))²) and (( respectively. Finally, we give the first PAA stringsum and allsum algorithms.
WLD-CFG CNF
Fig.
CFG CPG NE
CNF
controller WCFG
(a) Normal form results.
distrong equivalenoo
spinal TAG
CFG CPG
Fig.2
CFG CFG
NF NF
Stringsum
Allsum
(b) Stringsum and allsum results.
Figure 1: Overview of the results presented this paper. results shown in the paper; dashed
Solid lines lines are old results. An arrow X - means "X can be converted Y"; arrow X Y means "X has an algorithm for computing Y". We only show the conversions algorithms for CFG CFG; results for the other three two-level formalisms analogous.
CFGs controlled by CFGs, CFGs controlled by PDAs, PDAs controlled by CFGs, and PDAs controlled by PDAs are equivalent to TAG, LIG, PAA. and EPDA, respectively, in strict sense called d-strong equivalence (Butoi et al., 2023).
1 Introduction
Weir (1992) introduced a hierarchy of formal lan- guages whose first level (C1) is the class of context- free languages and second level (C2) is the class of tree-adjoining languages. Just context-free lan- guages can be characterized by both context-free grammars and pushdown automata, tree-adjoining languages are characterized by multiple formalisms as well, including tree-adjoining grammars (TAG; Joshi et al., 1975), linear indexed grammars (LIG; Gazdar, 1988), embedded pushdown automata (EPDA; ShjakeShanker, 1987), and pushdown- adjoining automata (PAA; Butoi et al., 2023).
When designing statistical parsers for tree- adjoining formalisms, it is often useful consider their semiring weighttd generalizations. In this paper, we introduce comiring-weightte versions of the above two-level formalisms, and we give new, more efficient algorithms for computing stringsums (the total weight of all derivations of string) in these formalisms.
Lang (1974) gives recognition algorithm for (what we call) simple PDAs, which can pop and push most one stack symbol. We have shown that this algorithm is suboptimal, and that (what we call) top-down PDAs, which always pop exactly one stack symbol, allow computing stringsums more
Tree-adjoiiiin languages can further be characterized through the mechanism of control (Weir, 1992), which yields various two-level formalisms. Specifically, we have shown that

---

efficiently (Butoi et al., 2022).
level formalisms ($5 and App. D).
Existing definitions of LIG (Vijay-Shanker and Weir, 1989 Joshi al., 1991; Kanazawa, 2014) are equivalent to CFGs controlled by simple PDAs, and existing recognition algorithms (e-g.. Vijay-Shanker and Weir, 1989) have the same limitation that makes Lang's algorithm suboptimal. By using a top-down PDA as a controller instead, we obtain a new stringsum algorithm that is more space-efficient and runs asymptotically faster. Additionally, obtain algorithm for allsums (the total weight of all derivations) that is more space-efficient.
Preliminaries
Let [i:j] denote the sequence of integers (G......)) If is a string, we write |s] for the length of s, 8; for the 7th symbol 8, and ((ej) for the substring
8:+1 1..
2.1 Weniring-Weiggted Languages
Throughout this paper, assume that W (W, A 0, 1) is commutative semiring. We also sometimes assume that W is w-continuous, which makes possible to take (countably) infi- nite sums. Please see App. A.I for definitions of these terms. Readers not familiar with semirings may safely assume that W = Rşo U {oo), , 0 = 0, 1 = 1, and + and @ are the usual addition and multiplication operations, respectively.
All stringsum algorithms that operate directly on EPDAs that we are aware of (Alonso et al., 2000, 2001) are designed for specific types of EPDAs, failing to take advantage of the structure of computation in top-down PDAs. We design new stringsum algorithm for a subclass of EPDA that is equivalent to top-down PDA controlled by top-down PDA, and we obtain both time and space improvements over these previous algorithms. Additionally, design a more space-efficient EPDA allsum algorithm.
Definition An alphabet Σ is a non-emply fi- nite set of symbols. A language over Σ a subset of E's Kleene closure Ex de Un2o E". A weighted language over E with weights from W (W, @ 8, 0, mapping from E' to W.
This paper considers weighted formalisms, where the weights are taken from W. Rather than just producing or recognizing strings from for- mal language, these formalisms define weighting function over Σ" When W is the boolean semiring ((0, 1}, V. O, 1). we recover the usual notion of a formal language defined as a set of strings.
Our algorithms assume that CFGs are given in Chomsky normal form, and for PDAs, we define a new normal form that exactly analogous to the Chomsky normal form. We show that applying these normal forms to controllers and controllees in- duces, for free, normal forms for the two-level for- malisms and for TAG, LIG, PAA, and EPDA. The conversions into the normal forms for all these for- malisms become simpler than direct conversions, they only require CFG PDA conversions. We leave extensions of our stringsum and allsum algo- rithms to general CFGs/PDAS for future work.
2.2 Weighted Context-Free Grammars
Definition 2. A weighted context-free grammar (WCFG) over semiring W (W, B 0, is tuple G (N, R, w. S), where N. E are finite sets of nonterminal symbols and terminal sym- bols, respectively, R S. - x (EU a finite set of productions. w:: R -> W is a production- weighting function, and S E N is the start symbol.
The main contributions of this paper are:
Semiring--eighted versions of the formalisms CFG CFG ($3), PDA CFG, CFG PDA, and PDA PDA (App. B.I).
We write production (X, a) E R as X + a,
Normal forms for these formalisms that arise, for free, from the normal forms of the controller/- controllee CFGs/PDAs ($3.2 and App. B.2). Stringsum algorithms for CFG CFG ($4), PDA b CFG, and PDA & PDA (App. C.2) that are more time-efficient or space-efficient than the existing algorithms for their equivalent LIG and EPDA.
and if w( X - +a) = we write X W a.
A WCFG produces strings by starting from the symbol S and repeatedly replacing the leftmost nonterminal with the right- hand side of a produc- tion X + a until no more nonterminals are left. In the following definitions, let G = EN, E,R, w, S) be WCFG.
The first stringsum algorithm for CFG PDA, and therefore, for PAA (App. C.2).
Definition 3. If 8,3 and a' B are sequences of terminals and nonterminals of G. where B1 E Σ* and Br E (EUN) and p
Algorithms for computing allsums in these two-

---

(x 7) production of G, we write a Ey a' to denote that a derives of in one step using production p.
3.1 Definition
A weighted labeled distinguished CFG (WLD- CFG) is simply WCFG where each production has a label, and its right-hand side has one "dis- tinguished" occurrence of nonterminal symbol. These two extensions allow its derivations to be controlled by another formalism.
Definition 4. A partial derivation in G from Ogg to On is sequence of steps d (x) Pi. Pu On.
We wrile Oo = On to assert that some partial derivation from Oxg to exists, or to denote the set of all such partial derivations. If Oxg = S and On -s E", we call a derivation of or that G derives
Definition 7. A weighted labeled distinguished context-free grammar (WLD-CFG) over semir- ing W (W, Q 8, 0, is tuple G (N Σ, L, R. S, where
The weight of is the product of its production weights,
N. E, and are finite sets of nonterminal symbols, terminal symbols, and labels, respec- tively,
w (d))
w (p:).
i=1
We denote by D(G, 8) the set of all derivations in G of s and by D the set of all derivations in G.
C (NUE)* is a finite set of productions,
w: R - W is production-weiighring func- tion, and
Definition The stringsum w(G, 8) of a string s under G is the total weight of all derivations in f 8,
S is the start symbol.
se w(d). GG,,8)
(ED(G,,)
(e, A, B1 Ba) is a production in R, we must have either 0, which we write as
Definition 6. The allsum w(G) of G is the total weight of all its derivations,
:: A B 3....
((G)
((d).
or 1 isiS S n and 3 E eN, which we write as
dED(G)
8: > 81 ... 1--33.3-111 Bn-
3 Semiring-Weightee CFG CFG
Weir (1992) defined hierarchy of formal lan- guages and showed that its second level, which is commonly known as the class of vee-adjoini lan- guages, can be obtained through the mechanism of control, using CFG (the controllee) whose deriva- tions are controlled by another CFG (the controller). In previous work (Butoi et al., 2023), extended this mechanism PDAs, both as controllers and controllees, and obtained four distinct formalisms by mixing a controller CFG or PDA with a con- trollee CFG or PDA. In this paper, we use semiring- weighted versions of these formalisms. We give a formal definition of weighted CFG CFG here (see App. B.1 for the other three definitions).
Weir (1992) gave two definitions derivation in an LD-CFG (the controllee) controlled by an- other CFG (the controller). In his first definition, the controllee nonterminals keep a record of the productions used, called control word (a string in L*). At the end of the derivation, each control word is checked for membership in the language of the controller. In his second definition, the controllee nonterminals run a controller derivation. When the controller generates label & E L,, it causes the controllee to apply production l. We use the latter definition, which allows one to think of the controller and the controllee as a single grammar, merging their productions into a single set of rules. For any sets X and V. define XD] [X[Y] X X, Y V'.. where X[Y] is just another way of writing the ordered pair of X and Y. If a Xi... .x.x, E X sequence of nonterminals, we use the notation ax [Y])... [ry]...x[[Y) for any Y e y
We denote such grammar by G G2, where G is the controller and G2 is the controllee. Additionally, we use symbols X, Y, Z, and a, b, c.... .. for nonterminals and terminals of the controllee, and A, B, C.... and a, b, c... for non- terminals and terminals the controller.

---

To make the following definition more readable. we assume that the controller's right-hand sides are either a single label or string of nonterminals, and that the controllee right-hand sides are either a single terminal or a string of nonterminals with exactly one distinguished position. It would be possible, but more tedious, to write the definition for the general case.
and the controllee WLD-CFG G2 with start symbol S2 and the set of productions
1: S2 4 A
4: A 1 a
l: S2 1 B$2C
4: B 4 l:: C c
R2
fz: S2 +
Dr
Definition 8. Let G₁ be WCFG with nontermi- nals N₁ and terminals L, called the controller, and let G2 be a WLD-CFG with nonterminals N2 and labels L, called the controllee. Then G1 >> G2 is a rewriting system with the following rules:
Below derivation of the string aabbcedd.
S2[S,] + S2[TLa]
S2|LiTL2L)
aS2 TL2
II (A B) is production of G1 where G E Ni. then G1 > G2 has a rule x[A.. " X[B for each X N
production of G1 and (e: X "3 a1 Yo2) is produc- tion of G2 then G1 D G2 has rule A(A..] w180U2 a (S] [S).
If (A "3, e)
aaB (151:////[LLL[((5/)))]..p..
aabbeedd.
Analogous definitions for when the controller is WPDA and/or the controllee is a WLD-PDA are given in App. B.1.
A derivation in G₁ > G2 starts with S|S). If there is rule then for any og E Σ', B2 E N2. and ag (EUNIWW)) write
(X[A-) 5 01 [ a22)
3.2 Normal Form
In this section, we define a normal form for CFG > CFG that will help us design fast stringsum and allsum algorithms. Interestingly, this normal form arises naturally from the normal forms of the con- trollec and the controller. Analogous normal forms derived for PDA CFG, CFG PDA, and PDA PDA in App. B.2.3.
an (A3g|a3 & agai 11
Similarly, if there is a rule p = (X[A] ") a), then for any og E E. and ag E (W)))[Wt))", we write
xox D anarg..
Definition 9. A WCFG is in Chomsky normal form if all of its productions are of one of the follow- ing types: (1) S + (2) X a, or (3) X + YZ, where S X, Y, Y,Z Z E N and E. Moreover, does not appear on the right-hand side of any production.
We write S to denote derivation with zero or more steps, as in Def. 4. S(S) + se E", we say that G G2 derives s.
Example 1. Consider the following G P G2 that generates the language dad controller is a WCFG Gj with the start symbol S and the set of productions
A WLD-CFG is in Chomsky normal form if all of its productions are of type (1) or (2) above, (3a) X + YZ, or (3b) X Y Z.
NJ. The
Proposition 1. For any WCFG Gj with weights in an w-continuous semiring, there is WCFG in Chomsky normal form that defines the same weighted language G
S 1 TL3
T 4 LTTL2
R1 =
T 1
For any WLD-CFG G2 with weights an w-contimuous semiring. there is a WLD-CFG Chomsky normal form that is equivalent to G2
L, + l
[1:3]
S 44 (4

---

G
22
G₁ P G2
name
S
L: S 22
S[S)
Wi @w2
(epsilon)
A
( X M4
[
Wig 6222
(terminal)
A W1
E
L: X M2 YZ
X X
20 @w2
S[-]Z[S]
(left pop)
A
W1
C: X
W2 YZ
201 @
[-5
(right pop)
A
MF
BC
X
X[BC..]
(push)
Figure 2: Normal form of CFG & CFG. Each row shows a rule from G1 (in Chomsky normal form) and possibly a rule from G2 (in Chomsky normal form) and the resulting normal-form rule of G2 & G2 along with its name.
Proof. See App. B.2.1.
that we are aware of.
Recall that CFG CFG is defined LD-CFG whose derivations are controlled by another CFG. When we consider only W(LD-)CFGs in Chomsky normal form, we obtain, for free, a normal form for CFG b CFG only by mixing their rules, as shown in Fig. 2. For the epsilon rule, in principle the left- hand side could be S[A] for any A, but such rules would never be used.
4.1 Pop Computations
In order to compute stringsums efficiently, we de- compose derivations into shareable smaller parts. Our decomposition is based on a concept that has been extensively used in the literature (Kuhlmann et al., 2011; Butoi et al., 2022) for decomposing runs of pushdown automata, namely pop computa- tions. In the context of WPDAs, pop computation partial derivation that has the overall effect of popping a single stack symbol, leaving the rest the stack unchanged (Butoi et al., 2022). We can define pop computations of CFG D CFG with a similar interpretation: partial derivations that "pop" single leftmost nonterminal symbol, leaving the rest of the nonterminals unchanged. We define pop computations of CFG CFG formally below. The pop computations of PDA CFG, CFG PDA. and PDA PDA are defined similarly; we present these in App. C.I.
Due to d-strong equivalence, this normal form also induces normal form for TAG. But, in order convert a TAG into the normal form, one needs first extract the controller and the controllee as shown by Butoi et al. (2023), then convert these to the Chomsky normal form, merge their rules, and convert them back to TAG, also shown by Butoi et al. (2023) (see App. E for complexity analysis of these transformations). Although these transformations add some extra complexity, the conversion into the normal form becomes simpler it only requires (LD-)CFG conversions, rather than direct TAG conversion. We leave a direct conversion for future work.
Definition 10. Let G1 be a controller WCFG and G2 be a WIDDCFG, with nonterminal alphabets N1 and N respectively. Let s Σ* be string of length 88) = n. A pop computation of G. 1 b G2 of XIA
4 Computing Stringsums
this section, we give a deduction system for com- puting stringsums of particular string CFG & CFG normal form. Stringsums of a string can be computed analogously 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 two- level formalism. Our algorithms have improved space requirements and run asymptotically faster than the best algorithms for LIG and EPDA. More- over, it is the only stringsum algorithm for PAA
type
where 0 siiijee Diisiskils
X. Y N2, and A E NN, is a pair of partial derivations (d1, d2), where
di E (X(A) = s(d M()
d2 E (12 ((a:)).
The weight of the pop computation w w(d1, d2) w (d1) ) & w(d2). A pop computation of type
x|A is a partial
derivation X[A) + 8(ka))

---

In words, a pop computation of a CFG D CFG pops a single controller symbol and derives string possibly with a gap. Fig. 3 shows a visual repre- sentation of a pop computation of a CFG > CFG.
Theorem 1. Let G1 be controller WCFG with nonterminal alphabet N and start symbol S, and G2 a WLD-CFG with nonterminal alphabet N Let 8 E Σ¹ be a string of length [8]
[Ax]
(a) The weight wo of an item
XIA
where X E
N2, and 0 S jijji n. is the total weight of all pop computations of this type.
[[a]
X(A-1
(b) The weight of an item
where
Sk
A N.N.X.YYE No. and 0 O S
Figure 3: A pop computation of a CFG & CFG is par- tial derivation possibly with a gap (the teal part). First, X [Ax] derives ((ask] and [[x]]. popping one nontermi- nal A. Then Y [[a] derives the gap (s.))) Finally, the purple part of the partial derivation resumes, deriving [(-]]- The weight of the pop computation is the weight of the purple part of the partial derivation.
k S k is the total weight of all pop computations of this type.
Proof. Define the span of item
X(A
to be i,
X|A
and that of item
to be i k:
We proceed by induction on the span f.
4.2 Deduction System
Base Case. When 1, the pop computation consists of a single step X [ - a. The weight of
We compute stringsums of CFG > CFG efficiently by exploiting the decomposable structure of the pop computations. We give the stringsum algorithm as a weighted deduction system (Goodman, 1999), shown in Fig. 4a.
is w(p) according to inference rule XJA
item
(terminal).
Items. The deductive system has two types of items, which correspond to the two types of pop computations (one with a gap and one without a gap). The weights of these items are the total weights of the pop computations of those types. Deduction rules. We distinguish several types of pop computations based on their first production and include a deduction rule for each. The weight each pop computation can be derived recursively from the weights of shorter pop computations. The weight of each deduction rule is the weight of the production in the side condition. Notice that the deduction system only shows how to derive further items, leaving the order in which these items should be derived by an algorithm unspecified.
Inductive Step. Assume that the statement holds for pop computations with span at most (e 1) and consider pop computations with span f. The weight of all pop computations of a certain type the sum of various cases, distinguished by their first production.
Starting with left pop rules. Any pop computa- tion starting with X [|A] and a left pop production p has the form (X[A) & Y[a) Z(S) - s(ga)))
By the inductive hypothesis, the weight wi of item Z[8)
is the total weight of all partial deriva-
tions such that Z - 8(skk By distributivity, the total weight of all pop computations of the above form w (p) & w1. This weight is added to the
Goal item. The goal item is
S19) which 0
x[A
stands for all derivations from SIS) to 8, where s) = n. Its weight is the total weight of all such derivations, which is exactly the stringsum.
weight of the item
in inference rule
(left pop).
Since the rules are symmetric, a similar argu- ment can be used for pop computations that start with right pop rules.
4.3 Correctness
We prove the correctness of the deduction system for CFG > CFG using the following theorem.
Starting with push rules. Any pop computation starting with x[A] and a push production p has the

---

name
(a) stringsum
(b) allsum
side condition
(epsilon)
SISS - E
818
(terminal)
X [A] _
X
X|
X
(left pop)
x[A.] S 11-1
X|A-]
X(A
Y[8]
Y|S
(right pop)
X[A-] = 2-
x|A-]
X(A
-
21-1
X -1
Y -1
X|8 -1
Y/C
2
11-
(push-1)
X X[A = X BC
X|A .]
X|A
2
X
X|8 -1
Y
(push-2)
X[A 5 x BC
X
Figure 4: Deductive systems computing stringsums and allsums of CFG CFG.
form (d1, d2), where
Y[G
ilarly, the weight w2 of item
is the
di X & X[BC|
(1a) Y
total weight of all pop computations (Y[C)
(1g) (yaj] 2 Y2,
(Jai) Z Yi 8(1=m)). By distributivity, the total weight of all such partial derivations is ((p) @ w2. This weight is added to the
d2 = r, Y2 - [[cm] Y2 [1:m]] (moo)]-
XIA
By the inductive hypothesis, the weight wi of item X
weight of the item
in inference rule
(push-1).
is the weight of all pop computa-
m
tions (X[B) A (0g) Y| T2, Y2 - 8(m))) Sim-
Any pop computation starting with X[A] and a

---

push production p has the form
the one used by Butoi al. (2022), resulting in an algorithm with the same runtime as ours. But, in order to do so, is necessary to store additional items, which increases the space complexity by an- other factor of [r]. Additionally, on the type of LIG used by Vijay-Shanker and Weir, we get a further runtime improvementof factor of ( For EPDA, our stringsum algorithm is more space-efficient than the algorithm of Alonso et al. (2001) by factor of [r] and has an improved run- time by a factor of [|], where [T) is the size of the stack alphabet. Their algorithm designed for an EPDA without finite-state control, which is equiv- alent to PDA > PDA where both the controller and the controllee are single-state. Therefore, we exclude the states when comparing the two algo- rithms.
x XIA] 1 X(BC
- ( 2
S (io)) 8 (juk] 22
- (i: (j.u) (ad)-
By the inductive hypothesis, the weight wi of item
x .]
is the weight of all pop computations
(0 22, T2 - ((ad)) while the (X
weight u2 of item
ric is the weight of all pop
computations [[C] S(ssk- By distributivity, the total weight of all such partial derivations is (()) wh truz, This weight added to the weight of the item
Computing Allsums
X(A)
inference rule (push-2).
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, CFGG PDA, and PDA D PDA can be computed similarly (see App. D). We define a new type of pop computation that will help us compute the weight all derivations instead of derivations of a particular string.
4.4 Complexity Analysis
Let X1 and X₂ be the sets of nonterminals stack symbols of the controllers and of the controllees, respectively. An algorithm based on one our deductive systems would would need to store a
x|A-]
weight for each item
and
for
Definition 11. Let G1 be controller WCFG and G2 WLD-CFG, with nonterminal alphabets N and N2, respectively. Let be symbol not occur- ring in the rules of Gn GG2 A pop computation of X(A
all k, E [0:n], A E X, and X, C X2, giving a space complexity of (n and O (n'|x (2)),, respectively. Overall we get space complexity of O(n') (()1))))))
type
where A E N1 and X, Y E N2 is pair of partial derivations (dl, d2), where
Computing the weight of each new item requires in the worst case inference rule (push-1), iterating over indices i, k. m, n E [0:n]. and symbols X, y 7 E X2 and A, B, C E X1. This gives a runtime of (n & 122 3))
di (X - 31 (2)
d2 C (Y,
_ 82)
4.5 Comparison with Existing Algorithms
where 81, E Σ' and T2 E Ni[N3] The weight of this pop computation is w(d1, d2) = w(1;) & w(dz).
Vijay-Shanken and Weir (1989) designed a recogni- tion (which is essentially computing stringsums in the boolean semiring) algorithm for a type of LIG that is d-strongly equivalent to CFG in Chom- sky normal form controlled by a simple PDA. Our stringsum algorithm is more spacc-efficient than theirs by a factor of [T] and more time-efficient by a factor of n|A),, where is the string length,
A pop computation of type is partial
derivation X{A] S 8, where E
Fig. 4b shows the deduction system for comput- ing allsums. Just as for stringsums, we distinguish
X(A -1
[ is the size of the stack alphabet, and [W] the size of the alphabet of nonterminals. Their algo- rithm could be improved using a trick similar to
two types of items, those of type
and
X|4

---

Theorem 2. Let G1 be a controller WCFG with nonterminal alphabet N and start symbol S, and G2 a WLD-CFG with nonterminal alphabet 2 Assume that both have weights in an w-continuous semiring (App. ). Then the allsum of G1 > 22
Limitations
Our stringsum algorithms can be used for LIG, EPDA, spinal TAG, and spinal PAA by first con- verting them to two-level formalism, converting the resulting controller and controllee grammar/au- tomaton into the normal form, and then merging their rules into single set of rules. Similarly, for general two-level formalism, the rules of the con- troller and the controllee would have be extracted from the merged rules, converted into the normal form, and merged back before using the stringsum or allsum algorithm. Although simpler, requiring only CFG and PDA conversions, these transforma- tions add some extra complexity. We leave direct normal form conversions for future work.
is the value of the item S19) 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 (Goodman, 1999) or the semiring generalization of Newton's 's method (Esparza et al., 2007).
Since there are various algorithms for computing item values, we don't analyze time complexity, but only space complexity. We and 2/ be the sets nonterminals or stack symbols of the controller and the controllee, respectively. As the algorithm
Ethics Statement
The authors foresee no ethical concerns with the research presented in this paper.
XIA
for each X, Y E 22 and A E N', and an item of the form X|A| for each X E N2 and A E N1, 1, it has space complexity of (I 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 (([N) items, therefore we have a space improvement of a factor of [W 1). Similarly, we get a space improvement for EPDA of a factor of W over the allsum algorithm based on Alonso et al.' 's (2001) algorithm.
needs to store an item of the form
References
Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume Prentice-Hal.
Miguel A. Alonso, Éric Villemonte de la Clergeric, and Manuel Vilares. 2001. A formal definition of bottom- up emhedded posh-down automata and their tabula- tion technique. Proceedings of the International Conference on Logical Aspects of Computational Lin- guistics (LACL), page 44-61.
Miguel Alonso, Éric Villemonte de la Clergerie, and Manuel Vilares. 2000. A redefinition of embedded push-down automata. In Proceedings of the Fifth International Workshop on Tree Adjoining Granmar and Related Frameworks (TAG+5), pages 19-26.
6 Conclusion
Our work has contributed several new results and algorithms for L2 formalisms. We intro- duced semiring-weighteed versions of controllable CFGs and PDAs, which give rise naturally to four semiring semiring-weighhed two-level formalisms when they are controlled by semiring-weighted CFGs and PDAs. We also introduced WPDA normal form that is completely analogous to the Chomsky nor- mal 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.
Y. Har-Hillel, M. Perles, and E. Shamir. 1961. On for- mal properties of simple phrase structure grammars. 14:143-172.
Alexandra Butoi, Ryan Cotterell, and David Chiang. 2023. Convergence and diversity in the control hier- archy. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Vol- une 1: Long Papers), pages 7597-7616. Association for Computational Linguistics.
Alexandra Butoi, Brian DuSell, Tim Vieira, Ryan Cot- terell, and David Chiang. 2022. Algorithms for weighted pushdown automata. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP).
Javier Esparza, Stefan Kiefer, and Michael Luttenberger. 2007. fixed point equations over commutative semirings. In Proceedings of the Annual Symposium

---

on Theoretical Aspects of Computer Science (STACS). pages 296-307.
Gerald Gazdar. 1988. Applicability of indexed gram- mars to natural languages. In Natural Language Parsing and Linguistic Theories, pages 69-94.
Joshua Goodman. 1999. Semiring parsing. Computa- Linall Linguistics, 25(4):573-606
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ull- man. 2006. Introduction to Automata Theory, Lan- guages, and Computation, 3rd edition. Addison- Wesley Longman Publishing Co.
Aravind K. Joshi, Leon S. Levy, and Masako Takahashi. 1975. Tree adjunct grammars. Journal of Computer and System Sciences, 166)
Aravind K. Joshi, K. Vijay-Shaneer and David J. Weir. 1991. The convergence of mildly context-sensitiee grammar formalisms. In Foundational Issues in Nat- ural Language Processing, pages 31-81.
Makoto Kanazawa. 2014, A generalization of linear indexed grammars equivalent to simple context-free grammars. In Formal Grammar, pages 86-103.
Marco Kuhlmann, Carlos Gómez Göddez-Rodriguez, and Gior- gio Satta. 2011. Dynamic programming algorithms for transition- based dependency parsers. In Proceed- ings of the 49th Annual Meeting the Association for Computational Linguistics: Human Language Technologies, pages 673-682. Association for Com- putational Linguistics.
Bernard Lang. 1974. Deterministic techniques for ef- ficient non-deterministic parsers. In ICALP 1974: Automata, Languages and Programming, pages 255- 269.
Harry Lewis and Christos Papadimitriou. 1997. Elements of the Theory of Computation, 2nd edition. Prentice-Hail. Hall.
Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2):165 165- 201.
K. ShankeS 1987. A Study of Tree Adjoining grammars. Ph.D. thesis, University of Pennsylvania.
K. Vijay-Shanker and David Weir. 1989. Recogni- tion of combinatory categorial grammars and linear indexed grammars. In Proceedings the First Inter- national Workshop on Parsing Technologies (IWPT), pages 172-181.
David J. Weir. 1992. A geometric hierarchy beyond context-free languages. Theoretical Computer Sci- ence, 104(2):235266

---

A Additional Preliminaries
A.1 Semirings
Definition 12. A monoid tuple (W, WW where W is a set, O an associative hinary operation, and E W, called the identity element, satisfies I & a a = a for all a E W. If for all a, b, we say that the monoid is commutative.
Definition 13. A semiring is tuple W (W,0,,00) 0, such that (W, C, 0) is commutative monoid and (W, @ 1) a monoid. Additionally, distributes over t. that a (b t c)
b t and
(a @ b) @ & e @ b 8 C, and absorbing with respect to 8, that is, 0 @ a - a @ 0 0. 1f 8 is commutative, then we say that W commutative.
The following definitions are from Esparza al. (2007):
Definition 14. IfW = (W, 0, 0, is semiring, the natural order on W is the relation S, defined such that < b + pE E W a o b. I is a partial order (i.e., refiexive, antisymmetric, and transitive), then we say that W is naturally ordered.
Definition 15. A naturally ordered semiring W = (W, B 8, 0, is w-continuous if is additionally equipped with an infinite summation operator + succ that:
For any countable sequence (a1, ..). the sequence
(+i ai) k20
has a least upper bound in
W and is equal + aj.
Multiplication distributes over infinite sums:
az) c
a, 2 c) a
For any partition (2,,2,,.. ..) N,
+ aj
IEI
A.2
Weighted Pushdown Automata
We use a definition of WPDA (Butoi al., 2022) that is more general than usual and roughly weighted version of the extended PDAs of Aho and Ullman (1972, p. 173) and the PDAs of Lewis and Papadimitriou (1997, p. 131).
Definition 16. A weighted pushdown automaton (WPDA) over semiring W W is tuple P (Q, E, w, Y.), (s)) where
Q. E, and I are finite sets of states, input symbols, and stack symbols, respectively.
d x x (EU x Q x 1* is finite set of transitions,
8 W is transition-weighting function, and
(1) and (gr,71) (g), where q. 41 E Q 9, I", are called the initial and final configurations.
If (p, 0, g, 4)) 8 is transition, write it as p 2 4. w(w - 9x) w., the notation p, g, -
a/w

---

We treat strings in I* as stacks, with the first symbol being the top of the stack and the last symbol being the bottom.
WPDA moves from one configuration to another by following transitions of the form (p. y S q, 7'), which represents a move from state to state ς. while scanning the symbol a, popping the se- quence 7 from the top of the stack and pushing the sequence 7'- In the following definitions, let P (Q,2, r,,, w, Yc), (gr: Ys)) be a WPDA.
Definition 17. A configuration of P is pair 7), where Q is the current state and I is the current contents of the stack. We write C(P) for the set of all configurations of P.
Definition 18. If (p: ya) and (q, 7/a) are configurations of P and (p: Y " w, (yy)) ) is transition of P, we write (p, yox) 3 (q: 7'))) to denote that configuration (q. 7xax) can be reached from (p, yox in step using transition т. Definition 19. We say that transition is k-pop, l-push if |y| k and |yy| = l. We say that seans a, and if a * E, we call scanning; otherwise, we call it non-scanning.
The following type of WPDA is weighted version of the PDA used by Lang (1974) for his recognition algorithm.
Definition 20. A WPDA is called simple if each of its transitions is k-pop, l-push for some k S 1 and I 1.
The following type of WPDA is weighted version of the PDA used by (Hopcroft et al., 2006) and others.
Definition 21. A WPDA called top-down if all of its transitions are 1-pop, and the initial and final configurations are (q,, S) and (qr,E), respectively.
Definition 22. A run of P from (40:70) to (gn, (n): is a sequence of steps (40: Yo)
Yo) - (ym: Yn) assert that a run from (p.7) (4, exists, to denote the (gny 7a). We write (go, 70) set of all such runs. If (go, 7o) Ye) and (4nr Yn) (gg, (g) we call accepting. I; scans og for E [1:n], then we say that scans = 0g ... On-
The weight of π is the product of its transition weights.
W( π
w(T)).
We denote by II(P, s) the set all accepting runs P scanning s, and by II(P) the set of all accepting runs of P.
Definition 23. The stringsum w(P, s) of string under P is the total weight of all accepting runs scanning s,
w(P, 8)
w(T).
TEII(P,))
Definition 24. The allsum w(P) P is the total weight of all its accepting runs,
w ((P)
w(T).
TCIl(P)
B
Two-Level Formal Systems
B.1 Definitions
Having defined both WPDA (Def. 16) and WLD-CFG (Def. 7), give definition for weighted PDA P CFG.
Definition 25. Lei P1 be controller WPDA with states Q, stack alphabet F and initial configuration (q,, Ye), and let G2 be controllee WLD-CFG with nonterminals No. Then P1 D G2 is a rewriting system with rules as follows.

---

(a) If (9.A 6/w0 7, is transition PI, then P1 D G2 has rule for each X E N2:
X A-1 S X1.
(b) If (r, A e/mi, 8,
)) is transition of PL. and (e: X "3 an Y Ya2) is production of G2, then G1 G2 has rule
[ A.. Swaz on [4., 7.l [(,, 002(0. Yi]-
Next, define WLD--PDAs by analogy with WLD-CFGs. This definition is weighted version of our previous definition (Butoi al., 2023).
Definition 26. A weighted labeled distinguished pushdown automaton (WLD-PDA) over a semiring W = (W, 0,0, 1) is tuple P = (Q, 6, w, (qi, S), (q),E)), where
Q. E, P and L are finite sets of states, input symbols, stack symbols and labels, respectively,
x Q x 1 is a finite set of transitions,
w: 8 + W is the transition- function, and
(q,,) and (gg,e). c). where Is Q, E T, are the initial and final configurations.
If (,, q, A, a, r, B .....B. -Bx) is transition in 5, we must have either i which we write as g, A 4 r. Bi B,, < S which write q, A 9 r, Bj B -.+ ... B,,.
WLD-PDA behaves similarly to a WPDA, but its runs are controlled by either controller CFG or PDA. As in $3, the rules of the controller and the controllee can be merged into single system.
Definition 27. Let G1 be controller CFG with nonterminals N and start symbol S, and let P2 be a WLD-PDA with stack alphabet I and states Q. Then G1 D P2 is rewriting system with rules as follows.
(a) If ", B) a production of G1, where N then G P2 has a transition for each X E r and q E Q:
4, X(A.A 8/W 4, 13.))
(b) If (A "1 f) a production of G1, and f: q, X a/wn r. an You is a transition P2 then G b P2 has a transition
q. X(A a/w1@w2
r, a. [S] Y[-1a211))
Definition 28. Let P1 be controller PDA with stack alphabet I and start configuration (.), and let P2 be WLD-PDA with stack alphabet T2 and states Q2. Then P1 Pa rewriting system with rules as follows.
(a) If (q, A s/w r) is a transition of P1, then P1 D P2 has a transition for each E N₂ and E Q2:
8/w0
p. X A..
p, X.r.
(b) If (r,A t/wn, s, 2) is transition of Pi, and l: P,X a/wa
q, on Y Yon is transition of P2. then
G P2 has transition
p. X (rrrA A.. a/wi a/wrr0my
g. a. la, 7:l Y(s, -. -a22gg yd)
The terms scamning/non-scammigg transitions and (accepting) runs are defined analogously to those for WPDAs.

---

B.2 Normal Forms
B.2.1 WCFG normal form
Proposition 1. For any WCFG G1 with weights in an w-continuous semiring, there WCFG Chomsky normal form that defines the same weighted language as G1. For any WLD-CFG G2 with weights in an w-continuous semiring, there is a WLD-CFG Chomsky normal form that is equivalent to G2.
Proof. The proof for WCFGs is generalization of the standard conversion for unweighted grammars (Hopcroft et al., 2006), and is related to the Earlcy-style algorithm of Stolcke (1995).
1. If S' is the old start symbol, add new nonterminal S", production S' - S, and make S' the new start symbol.
2. For every terminal a, create a production To + a, where Ta a fresh nonterminal, and replace every right-hand side occurrence of a with Ta.
3. Replace every production X 4 Y1 ... YR. where 2, with the productions
X " Yı
71 1, Y272
Zg 1 Yx 1k
where Z1, Z are fresh nonterminals.
4. For each nonterminal X, compute the weight of all partial derivations X S uusing the deductive system
A m
A
B
A [4 B
A
c
A "h BC
E) = Wzz add productions Then for every production " Y Z with w(Y + E) = wy and w(Z 4)
X wi Biwwy, Z and X wiewx, Y. Finally, for all X, remove all productions X +
5. For all nonterminals X and Y, compute the weight of all partial derivations X Y using the deductive system
A A
1
B B C
Then for every production X 122, YZ and nonterminal W * X, with w(W & X) = Wi, add production W
wi Swy YZ. Finally, for all X, Y, remove all productions X - Y.
Now give similar construction for WLD-CFGs. Let G be WLD-CFG and F controller WCFG WPDA, both with weights from an w-continuous semiring. Then there exists WLD-CFG in normal form G' and a controller F' such that & G' defines the same weighted language as G. We assume for simplicity that F is a controller WCFG; a similar construction can be given when it is a WPDA.

---

Converting a CFG CFG normal form requires an allsum algorithm that works on any binarized CFG CFG, not necessarily in normal form. We must use the rules shown in Fig. in addition to those from Fig. 4b when computing allsums.
(nullary)
[ "
(controllce unary)
X[A-] 4 Y
XIA
X(B
(controller unary)
X(A-] " X[B
X
Figure 5: Additional deduction rules for computing allsums in binarized CFG CFG.
Root-foot transform The nullary and umary removal steps below analogous to nullary and unary removal in WCFG. However, sometimes, when we remove nullary/unary rules, we need information from both the controller and controllce compute their lost weight. To facilitate this, we define the following transformation, which copies information from the controllee to the controller.
Let N and 22 be the controller and controllee nonterminal alphabet, respectively.
1. For every controllee rule é X where a has distinguished symbol, relabel the rule e/.
2. For every controllce rule é X + Y B. relabel the rule as ex-
3. Perform the construction of Bar-Hillel et al. (1961) on the controller, using controllee nonterminals instead of states. That is, relabel every controller nonterminal A as A or A for all X, Y c making as many copies of rules as needed, subject to the constraints that (i) if the Ihs is A (where Y could be 1) then the first rhs symbol must be A and the last rhs symbol must be A (ii) if A is rhs nonterminal then its successor (if any) must be B
4. Add a new controller start symbol S' with rules S + S for all X N2.
Controllee binarization In the controllee, replace every production é X " 11... Ya ... Yt, where
k > 2, with the productions
( X "4 1iZ
f2: Z1 1 1222
(d-1: : Za- 1 Y4 Z
la Za 1, 2 Yk
tai1 : Zd11 1 2d12 Yk-1
4x 1 7 1 Y Yai1

---

where ....., Z are fresh controllee nonterminals. Accordingly, in the controller, replace every rhs occurrence of & with & ..... f2-1-
Controllee nullary removal Like the standard nullary removal algorithm (Hoperoft et al., 2006), nullary removal in an WLD-CFG has three steps: partitioning, precomputation, and removal. However, removing nullary rules from the controllee also sometimes requires modifications to the controller.
1. Partition: Replace every controllee nonterminal X with two nonterminals X and Xy. Every rule with & rhs nonterminals becomes 2 rules with all possible combination of rhs nonterminals, and the Ihs annotated iff the rhs is empty or all the rhs symbols are annotated The start symbol is Sz.
2. Precompute: Compute the allsum
X-
for all A c W1,, Xg C N22-
3. Remove (non-distinguished); For every non-distinguished occurrence of Xg in the rhs of controllee rule π, delete the occurrence and multiply the weight of by X.
4. Remove (distinguished): The distinguished occurrences of Xe cannot be removed in the same way, because we don't it know what weight to multiply in. Instead, perform the root-foot transform. Then, for every occurrence of A. on the rhs of controller rule delete the occurrence and multiply the weight of x by
5. Remove (start): Add controller rule S' 4 and controllee rule é S 2 E, where w = w
8x(88
6. Remove every controller rule S' ->> E.
7. Remove every controller rule with Ihs A and every controllee rule with lhs Xe.
Controllee unary removal
1. Partition: Replace every controller nonterminal A with two nonterminals Ay and Ay. Every rule with rhs nonterminals becomes 2 rules. rule's annotated iff all of its rhs symbols are either labels controllee unary rules or annotated U. The controller temporarily has two start symbols, Su and Sy.
X|Au x.]
2. Precompute: Compute the allsum
for all Au E NN, EN2.
3. Remove (controller): Perform the root-foot transform. Then, for every occurrence of Au on the
Auix
rhs of rule π,, delete the occurrence and multiply the weight of π by w
Remove all
rules with lhs X
4. Remove (controllee): Remove all unary rules, and for each rule é Y " a and all X N2, make copy E: X w a.

---

B.2.2 WPDA normal form
We first define WPDA normal form that is analogous to Chomsky normal form for WCFGs.
Definition 29. A WPDA is in normal form if all of its transitions are of one of the following types: (1)
g,,E, E, (2) scanning and O-push, or (3) non-scanning and 2-push. Moreover, S is not pushed by qu: S 5/m
any transition.
A WLD-PDA is in normal form if all of its transitions are of type (1) or (2) above, (3a) q, X g/w r, Y Z.
8/10 r; Z. or (3b) q, X
Proposition 2. Let P be a WPDA with weights from an w-continuous semiring. Then there is a WPDA normal form that defines the same weighted language as For any WLD-PDA P2 with weights in an w-continuous semiring, there is a WLD-PDA in Chomsky normal form that is equivalent to P2-
Proof. In previous work (Butoi et al., 2022), we gave conversion from arbitrary WPDAs to normal form that is close Def. 29, but allows transitions that scanning but are 1 1-push 2-push. We modify the conversion using the following preparatory steps:
1. If (gu, 71) is the old start configuration, add a new state q',, new stack symbol S and a transition q'' 1 4s Yo. and make (q.'S") the new start configuration.
2. For every terminal add fresh stack symbol Ta. Replace every scanning transition (q, X a/w r, 7) with (q, X r, To7), and add transitions (q, Ta 0/1 q, for every state q.
3. Remove all nullary transitions (Butoi et al., 2022, $3.2).
4. Remove all unary transitions (Butoi et al., 2022, $3.3).
A WLD-PDA can always be converted into equivalent WLD-CFG (Butoi al., 2023), converted into the normal form, then converted back into into WLD-PDA.
To convert WLD-PDA to normal form, we use the construction above, modified by analogy with Prop. In the foot-foot transform, each nonterminal includes two or four states (just as allsum items do). The nullary removal procedure for WPDAs is more complex than for WCFGs, but the required modification is analogous: we remove non non-distinguished stack symbols X. as usual, but when removing a distinguished stack symbol Xg, we must multiply its weight in the controller rather than the controllee.
B.2.3 Two-level normal forms
Fig. 6 shows how the normal forms of PDA CFG, CFG PDA and PDA > PDA are obtained from the normal forms of the controllees and the controllers. For the epsilon rules, as noted in $3.2, in principle there could be rules with other left-hand sides, but such rules would never be used.
Computing Stringsums
C.1 Pop Computations
Definition 30. Lei P be controller WPDA with states Q, and stack alphubet I, and let G be a WLD-CFG
with nonterminals N. Let s E Σ* be string of length |s] A pop computation P P G of type
X/p, A.
where sisiskslsnpe X and A E T, is a pair of partial
derivations (d1, d2), where
di c (X A] 3 8(()) v))
d2 (Y, - ((mg))

---

Pi
G2
P1 G2
46
t/w1
f
8: "3
Slq.: S)
wi 0bw2,
(epsilon)
A
f/wi
t; X 33
X [p, A
wi wwww2
(terminal)
P. A
8/101
9,E
f: X "23 YZ
[p, A..
ui mr2,
-| qu: S)
(left pop)
P, A
t/W1
9,E
8: X "3 YZ
X A..]
wi 0100
Y(a, 7)
(right pop)
p, A 6/WI,
q; BC
[g. A..]
W1 X(q, BC
(push)
(a) PDA CPG.
G
P2
G1 D P2
name
S
MI
E/w3 9 t: qu
4, S[S]
E/ E/W18W2
Af:
(epsilon)
A
W1
l
t: q, X
a/wa, T
9, 9AA
a/wi @uy
T,E
(terminal)
A
f: q, X
s/w2,
r. Vz
4, .
E/ c/WIS Soura
r, [[-]
(left pop)
A
WI
8: q, X
c/w2
r, Y
4, [
3/w1&00
r, Y(S [
(right pop)
A
101
BC
9, X [-
E/YCN XBCC
(push)
(b) CFG PDA.
Pi
P2
P D P2
name
8/w1
s/ur
5/w180w2
d.
S
90.
8: S.SS S
S S
27. a/WISSun
(epsilon)
8/wl,
o/w2
A
E
t: X
8,E
Xp, A
8,E
(terminal)
8/0m
s/um
P,
E.E
E: r, X
8, Y
r, X A.
s, Y [g. :. [g] S]
(left pop)
8/w1
8: r. X s/w2,
E/W18W02
p,
A
9,6
8, Y
r, X [p, A..]
8, Y(g! ()
(right pop)
8/wI
E/WI
A
4, BC
X [p. A..]
X X(q, BC
(push)
(c) PDA PDA. States qt and of are the initial states of P and Pz, respectively, and similarly for df and oî-
Figure 6: Normal forms of PDA b CFG, CFG PDA, PDA PDA resulting from normal forms of their controllers and controllees.

---

X/p.A. : A pop computation of type
is a partial derivation [p, A 3 ((al]
Definition 31. Let G be a controller WCFG with nonterminals N, and let P be a WLD-PDA with states Q and stack alphabet I. Let & E E" be inpul string of length [s] = A pop computation of G v P of )
type
where 0 Snskksssnppe
Yer, and E N, a pair of
3.4 R.
(TT1, T2), where runs
#1 c ((p, x(A)) 3 (q, ( (()) and scans [(ey]
22 ((r; 22 3 (s, E) and scans (J:d)
pop computation of rype
X(A
run (p. x[A)) & (g, E) scanning (i:s)-
i.p
1.
Definition 32. Let P1 be a controller WPDA and P2 be a WLD-PDA, with states and stack alphabets Q
and 1, and Q2 and 2, respectively. Let 8 E E. be an input string of length [s] = n. pop computation
X(a.A-]
of P1 > P2 of type
where S i S k S p.qrrs Q2 e,f E Q1.
5.2
X, Y E 22 and A E Tú, is a pair of runs (T2), where
Th X(e, A)) = (g. {)), and scans ((1))
((r, 12) E) and scans [k::]].
A pop computation of type is run (p. ((e, A) - (g,E) scanning ((a)]
C.2 Deduction Systems
Figures 7 to 9, in the columns labeled "stringsum," show deduction systems for computing stringsums PDA & CFG, CFG PDA, and PDA PDA. The controller and controllee PDAs are assumed be single-state.
The goal items for PDA & CFG, CFG PDA, and PDA PDA are, in order,
Sla..
SIS
and
n.
8lo 8
where n is the length of the input string.
D Computing Allsums
Definition 33. Let P be a controller WPDA with states Q and stack alphabet I, and let G be a WLD-CFG
Alp,
with nonterminal alphabet N. pop computation o > G of type
where X, Y E,,
P, q E Q, and Ae F, is pair of partial derivations (d1, d2), where
di E (X(p, A] - 81 Y (g.
d2 E (Y2
- 82)
and 31, 82 E Σ', Y, E N[ The weight of this pop computation w(d,, d2) w((1)) & w(2)). XIp.Al is partial derivation X(p, A - 8. where 8 Σ'
A pop computation of type

---

name
stringsum
allsum
side condition
(epsilon)
0
8 $ ">
5/g. Sl
5lg. 5]
(terminal)
X A] ">
Xlp, Al
X(p, A
Zlg.. 8
&
(left pop)
X [p, A-] - 1la.-1Zla.. S)
X|p. A -]
X|pAA
Yla."
Y Vlg.
(right pop)
X/o, A.. 1 Yla. (a.
X|p. A -
X|p.A
Alg
X(g. 8 -1
r/r G -]
X
0
2
Y|
26. 9
(push-1)
X A.) 5 X(q. BC
XIp. -]
X(p.A
X(g. B -]
Xla. 8
Y/r q
0
Y(r. -
(push-2)
X|e, A.. X(g, BC
Figure 7: Deductive systems for computing stringsums and allsums of PDA CFG. State g. is the initial state of the controller.

---

name
stringsum
allsum
side condition
(epsilon)
0
q.. S(S]
f/1
9
8/5.
8[5]
0,
0,
91
(terminal)
q,E S [|
a/w,
S|S
8
(left pop)
X ((A
Y[-IZ[S)
X[A -1
X(A -1
1.P
N.4g
S
Y[S
(right pop)
4.9
5.
X [A-]]
6/W
([S]
X
X(A
Ry
X -1
VIG -]
8
Y[C
2
(push-1)
X [A..]
6/W
X [(BC.
X[A
X|A []
2
i.p
a
X ..)
X -1
VIG
Yl+
Y
J.r
(push-2)
3.
6
P. 6/w
9. BC
XIA
X|A
f
Figure Deductive systems for computing stringsums and allsums of CFG PDA. States g, and Øs are the controllee's 's initial and final states, respectively.

---

Dame
stringsum
allsum
side condition
(epsilon)
72
q.. S]
4/m
gr.5
Sla 8)
866
(terminal)
8:
e/m 9.5 X. A)
X/e.A
1.
1.9
zlot S
2/
Ar
X(e, s/w Vlf.-12l.. S
(left pop)
X/e.Ao|
A
4.
8,5
R. S.r
Vloe S]
Yig. SI
(right pop)
X(e A.. 4/w Yff. S|2ga
A
6.9 Scr
X
Vlg. C
xlz.8 1
Ybu.
Vlo
1.0
(push-1)
mus
1.
X(e, A(c,A.) A.. s/w BC.)
(6, A
Aod
x 1,1
-]
xin. 01
Igy-1
Vlu.C
3.4
3.r
(push-2)
J.P
R
A(e s/m, 9. XIf,
Xle,
A
Xlc.
Figure 9: Deductive systems for computing stringsums and allsums PDA PDA. States q! and 9² are the initial states of P, and P2, respectively. State Øf is the final state of P2.

---

Definition 34. Les G be a controller CFG with nonterminal alphabet N, and let be WLD-PDA with X[A.)
states Q and stack alphabet T. A pop computation of D P of type
where X, Y C
Ps P.9, E Q and A E N. is a pair of runs (TI, T22,, where
m ((P, - (g. ((=)(2) and scans $1
E ((r, T2) - (s)))) and scans $2
and $1, 82 E', I2 E TWW".. The weight of this pop computation W(T1, w((r)) w(TT))
pop computation of type
X(A)
run (p, x(A) - (q,6) scanning some 8 E E".
Definition 35. Let P1 be controller WPDA and P2 WLD-PDA. Additionally, let Q1 and 1, and Q2 and 22 be the states and stack alphabets of P1 and P2, respectively. A pop computation of P1 & P2 A-e
of type
YIr.
where p,q,r,8 Q2 e, E Q1, X, Y,E and A E [1, is is a pair of runs
(T1,TT) where
# E ((p. A) 7 (g. (2)) and scans 81
#2 E ((r, 12) = (s,E)) and scans $2
and 81, 82 C E', Y2 C [2[T The weight of this pop computation is w( R2) w(T)) & w(T2).
pop computation of type Xle.A is run (p, Xee A)) - (q, scanning some s E Σ"
Figures 7 to 9, in the columns labeled "allsum", show deductive systems for computing allsums PDA CFG, CFG >> PDA, and PDA & PDA. As in $5, the value of the goal item can be computed by fixed-point iteration or the semiring generalization of Newton's 's method.
E Complexity Analysis of Conversions
Our stringsum and allsum algorithms, although designed for the two-level formalisms, can also be used for TAG, LIG, PAA, and EPDA. However, we must apply a series of conversions in order to do this. For instance, we must apply the following transformations to WLIG with sets of nonterminals W and stack symbols r before feeding it into the stringsum algorithm:
1. The controller WPDA and the controllee WCFG have to be extracted from the WLIG, resulting in WCFG with ((W)) nonterminals and WPDA with O(T)) stack symbols.
2. The controllee WCFG must be converted into Chomsky normal form. If the productions have at most k symbols on the right-hand side, then the output WCFG has O x (R]) nonterminals. Similarly, the controller WPDA must be converted into the normal form. If the WPDA has transitions that push at most k symbols, the resulting WPDA has O [8]) states.
3. The rules of the controller and of the controllee need be merged back into set of WLIG rules. This construction outputs a WLIG with ((N) x (Q)) nonterminals and ((F)) stack symbols, where N is the set of nonterminals of the input controllee, and Q and I' are the sets of states and stack symbols of the input controller.


Reviews:
[{"review_id": "kzTYPYe92J", "reviewer": "Reviewer_F4Ew", "summary": "", "questions": "A.\nThere is something about the definitions of WLD-CFG and WLD-PDA that confuses me: these two definitions are not fully symmetrical as I was expecting. WLD-CFG has special rules X[A..] -> X[..] that are used to simulate non-scanning transitions of the PDA controller, or else are used to simulate leftmost derivations of the CFG controller when the sentential form starts with a nonterminal. What is the corresponding feature for WLD-PDA?\n\nB.\nd-strong equivalence is mentioned in two places in this draft, and seems a very important notion related to your findings. Unfortunately, there is no definition of d-strong equivalence in this draft, as far as I can tell. \n\nC.\nThere is a technical problem with your definition of pop computation. As an example, consider definition 24 where the controllee is a WLD-CFG and the controller is a WPDA. In derivation d the controller moves from configuration (q, A\\gamma) to configuration (q, \\gamma). However, it could well be that at the intermediate steps the topmost symbols of \\gamma are popped from the stack and later replaced by exactly their same copies (by some push transition). Those computations have type [i,X,A,j,k,Y,l] according to your definition, but are *not* accounted for by your deductive rule system in figure 2. The idea that pop computations should not 'consume' the part of the stack \\gamma below A has been extensively discussed in the literature, see for instance Kuhlmann, Gómez-Rodríguez, Satta 2011, Dynamic Programming Algorithms for Transition-Based Dependency Parsers, and references therein. You have a similar problem in the related definitions in section 5.  \n\nD.\nThere is an overloading between the signature [i,X,A,j,k,Y,l] that you use to indicate types for pop computations, and the notion of item [i,X,A,j,k,Y,l] used by your deductive rule system. Of course these objects have related meaning, but I think you need to resolve this conflict. \n\nE.\nI think there is a problem with theorem 2. The theorem establishes a correspondence between items and pop computations together with derivations of the form Y[\\alpha] =*=> s(k:l]. However, notice that the derivation Y[\\alpha] =*=> s(k:l] is not checked by your deductive rule system: this is apparent from rules (22) and (23) where you make a 'guess' on the extension of the gap (i--j in rule 22) without checking for the existence of the associated derivation. \n\n-------\nThis part written after the Author responses:\n\nA: ok.\n\nB: I am already familiar with the notion of d-strong equivalence, double dot notation for LIGs, etc.  My point is that this draft is not self contained: the average ACL reader will not be able to understand your theoretical developments without a basic discussion of the above notions. Using specialised mathematical notation without providing a few lines of explanations, as those that you wrote in your response, does not meet the standard of scholarship of the EMNLP conference. I recommend you fix this in the final version, if you have extra space. \n\nC: the new definition is ok.\n\nD: ok.\n\nE: you are right, sorry I misread steps (22) and (23).  You should be aware that the implementation of your deductive rule system should ensure that computation of weights w[j,Z,k] should be completed before undergoing steps (22) and (23). \n\nAccordingly, I have changed my overall score from 2 to 3. I wanted to provide 3.5, but this option is not available.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments and feedback! We greatly appreciate the time and effort put forth in order to understand our paper in detail and help us improve it. \n\n# Responses to \"Questions For The Authors\"\n\n### A. There is something about the definitions of WLD-CFG and WLD-PDA that confuses me: these two definitions are not fully symmetrical as I was expecting. WLD-CFG has special rules X[A..] -> X[..] that are used to simulate non-scanning transitions of the PDA controller, or else are used to simulate leftmost derivations of the CFG controller when the sentential form starts with a nonterminal. What is the corresponding feature for WLD-PDA?\n\nWe apologize for not explaining this point more clearly.The definitions of WLD-CFG and WLD-PDA are fully symmetrical. You mentioned a rule of the form $X[A \\cdot \\cdot] \\rightarrow X[\\cdot \\cdot]$, which simulates the application of a production rule/transition of the controller CFG/PDA, without the application of any rule of the controllee. \n\nThe WLD-PDA counterparts would be $p, X[A \\cdot \\cdot] \\xrightarrow{\\varepsilon} p, X[\\cdot \\cdot]$, for a CFG controller, and  $p, X[r, A \\cdot \\cdot] \\xrightarrow{\\varepsilon} p, X[s, \\cdot \\cdot]$, for a PDA controller. You can observe this symmetry more clearly in Figure 1, where there is a one-to-one correspondence between the rules of the four formalisms. The types of rules that you mentioned are stated in equations (5), (10), (15), and (20). We will add some extra explanations in the revised version.\n\n### B. d-strong equivalence is mentioned in two places in this draft, and seems a very important notion related to your findings. Unfortunately, there is no definition of d-strong equivalence in this draft, as far as I can tell. \n\nThe definition of d-strong equivalence is indeed crucial for our findings. The definition was originally introduced by Butoi et al. (2023), together with the definitions of the two-level formalisms, which we extended to the weighted case in our paper. We agree that our paper would be improved by providing this definition and we will do so in the final version. \n\n### Section 3 introduces two-level formalisms without much discussion of the intuition behind the formalisms. I think this makes it very difficult for the reader to follow the developments of your findings. For instance, the intuition behind the tilde notation on rules is not presented. Same thing for the double dot notation that appears for the first time at l.230 and is used later on in your proofs. \n\nYou mentioned that Section 3 introduces the two-level formalisms without much intuition behind them. The two-level formalisms are not our contribution, they were introduced in Butoi et al. (2023), which contains a much more detailed presentation, including some informal explanations. Our contribution in this paper is a weighted version of their definitions. The double dot notation which first appears in line 230 is standard in the context of LIGs. The double dots represent an arbitrary sequence of stack symbols. The nonterminal symbols with a breve (we think that’s what you mean by tilde) on top are called distinguished nonterminals and they were first introduced by Weir (1992), and then used also by Butoi et al. (2023). The distinguished nonterminal is the nonterminal on the right-hand side of a controllee production which receives the controller sentential form/configuration after the application of the production.\n\n### C. There is a technical problem with your definition of pop computation. As an example, consider definition 24 where the controllee is a WLD-CFG and the controller is a WPDA. In derivation d the controller moves from configuration (q, A\\gamma) to configuration (q, \\gamma). However, it could well be that at the intermediate steps the topmost symbols of \\gamma are popped from the stack and later replaced by exactly their same copies (by some push transition). Those computations have type [i,X,A,j,k,Y,l] according to your definition, but are not accounted for by your deductive rule system in figure 2. The idea that pop computations should not 'consume' the part of the stack \\gamma below A has been extensively discussed in the literature, see for instance Kuhlmann, Gómez-Rodríguez, Satta 2011, Dynamic Programming Algorithms for Transition-Based Dependency Parsers, and references therein. You have a similar problem in the related definitions in section 5. \n\nYou are correct - thank you for spotting this! Indeed, we meant that $\\gamma$ from your example should not be touched in any intermediate configurations of the controller. This is reflected in our deduction system, which only accounts for this type of derivation. The correct version of Definition 24 is the following:\n\nLet $\\mathbf{F}_1$ be a WLD-CFG, $\\mathbf{F}_2$ a controller WPDA with a single state $q$, and $\\mathbf{s} \\in \\Sigma^*$ a string of length $|\\mathbf{s}|=n$. A pop computation of $\\mathbf{F}_2 \\triangleright \\mathbf{F}_1$ of type $[i,X,A,j,k,Y,l]$, where $0 \\leq i \\leq k \\leq l \\leq j \\leq n$, $X,Y \\in \\mathcal{X}_1$, and $A \\in \\mathcal{X}_2$, is a derivation $d = X_0[q, \\gamma_0],\\Upsilon_1 X_1[q, \\gamma_1] \\Upsilon’_1, \\ldots, \\Upsilon_m X_m[q, \\gamma_m] \\Upsilon'_m, \\ldots, \\mathbf{s}(i,j]$ of the substring $\\mathbf{s}(i,j]$, where $X_0=X$, $X_m=Y$, $\\gamma_0=A \\gamma_m$ and for all $l<m$, $|\\gamma_l| \\ge |\\gamma_0|$, such that there is a derivation $d' =  Y[q, \\gamma], \\ldots, \\mathbf{s}(k,l]$ of the substring $\\mathbf{s}(k,l]$. A pop computation of type $[i,X,A,j,\\bot,\\bot,\\bot]$ is a derivation $d = X[q, A], \\ldots,\\mathbf{s}(i,j]$.\n\n### D. There is an overloading between the signature [i,X,A,j,k,Y,l] that you use to indicate types for pop computations, and the notion of item [i,X,A,j,k,Y,l] used by your deductive rule system. Of course these objects have related meaning, but I think you need to resolve this conflict. \n\nWe will consider rewriting the definitions of pop computations in the revised version such that they don’t include the signature [i,X,A,j,k,Y,l] and keeping the items only in the deduction system, similar to Kuhlmann et al. (2011).\n\n### E. I think there is a problem with theorem 2. The theorem establishes a correspondence between items and pop computations together with derivations of the form Y[\\alpha] ==> s(k:l]. However, notice that the derivation Y[\\alpha] ==> s(k:l] is not checked by your deductive rule system: this is apparent from rules (22) and (23) where you make a 'guess' on the extension of the gap (i--j in rule 22) without checking for the existence of the associated derivation.\n\nThe deduction system computes weights of derivations with a “gap”, where the weight of the gap is not accounted for (otherwise we would overcount some parts of the derivations when deriving the weights of other items). The derivation Y[\\alpha] ==> s(k:l] is not checked by our deduction system because this derivation represents the gap of a pop computation. But, if such a derivation exists, its weight will be used to compute the weight of the full derivation, including the gap.\n\n# Response to \"Typos, Grammar Style, And Presentation Improvements\"\n\n### Proof of theorem 1: I don't really see the need for this proof, why don't you just say something like 'directly follows from the definition of item'?\n\nRegarding the proof of Theorem 1, we find it necessary for proving the correctness of the deduction system. While it is true that we provide an informal description of the items of the form $[i,X,j]$ and their weights in lines 457--461, we currently don’t have any other formal definition for this type of items (we currently only have definitions for pop computations and their corresponding items), therefore the theorem formalizes this intuition. The proof also does not immediately follow from the definition, as it requires the application of rule from equation (25) (although, we do agree that this step is straightforward).\n\n### 184: your definition 9 is not used anywhere else in the draft, as far as I can see ... I wonder why you want to have a numbered definition for some notion that is never used. \n\nYou mentioned that the simple PDA introduced in Definition 9 is not used anywhere in the paper. The type of LIG used by Vijay–Shanker and Weir in their parsing algorithm is equivalent to an LD-CFG controlled by a simple PDA. The simple PDA does not allow computing stringsums efficiently (this is explained in more detail in Butoi et al. (2022)), therefore two-level formalisms having such controller PDAs have the same issue. We agree that we should explain this point in greater detail and we would be happy to do so in the final version. \n\n\nWe also thank you for spotting the typos (e.g., the ones in lines 150, 164, 302, etc.) and the missing references (e.g., Kuhlmann et al., 2011, Butoi et al., 2022 for pop computations) in the current version of the paper and for your suggestions (e.g., for lines 456-457).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Novel results, interesting combination of existing techniques.", "reasons_to_reject": "Technical presentation is not carefully developed, some parts of the draft are confusing or mistaken, and need further elaboration.", "questions_to_authors": "A.\nThere is something about the definitions of WLD-CFG and WLD-PDA that confuses me: these two definitions are not fully symmetrical as I was expecting. WLD-CFG has special rules X[A..] -> X[..] that are used to simulate non-scanning transitions of the PDA controller, or else are used to simulate leftmost derivations of the CFG controller when the sentential form starts with a nonterminal. What is the corresponding feature for WLD-PDA?\n\nB.\nd-strong equivalence is mentioned in two places in this draft, and seems a very important notion related to your findings. Unfortunately, there is no definition of d-strong equivalence in this draft, as far as I can tell. \n\nC.\nThere is a technical problem with your definition of pop computation. As an example, consider definition 24 where the controllee is a WLD-CFG and the controller is a WPDA. In derivation d the controller moves from configuration (q, A\\gamma) to configuration (q, \\gamma). However, it could well be that at the intermediate steps the topmost symbols of \\gamma are popped from the stack and later replaced by exactly their same copies (by some push transition). Those computations have type [i,X,A,j,k,Y,l] according to your definition, but are *not* accounted for by your deductive rule system in figure 2. The idea that pop computations should not 'consume' the part of the stack \\gamma below A has been extensively discussed in the literature, see for instance Kuhlmann, Gómez-Rodríguez, Satta 2011, Dynamic Programming Algorithms for Transition-Based Dependency Parsers, and references therein. You have a similar problem in the related definitions in section 5.  \n\nD.\nThere is an overloading between the signature [i,X,A,j,k,Y,l] that you use to indicate types for pop computations, and the notion of item [i,X,A,j,k,Y,l] used by your deductive rule system. Of course these objects have related meaning, but I think you need to resolve this conflict. \n\nE.\nI think there is a problem with theorem 2. The theorem establishes a correspondence between items and pop computations together with derivations of the form Y[\\alpha] =*=> s(k:l]. However, notice that the derivation Y[\\alpha] =*=> s(k:l] is not checked by your deductive rule system: this is apparent from rules (22) and (23) where you make a 'guess' on the extension of the gap (i--j in rule 22) without checking for the existence of the associated derivation. \n\n-------\nThis part written after the Author responses:\n\nA: ok.\n\nB: I am already familiar with the notion of d-strong equivalence, double dot notation for LIGs, etc.  My point is that this draft is not self contained: the average ACL reader will not be able to understand your theoretical developments without a basic discussion of the above notions. Using specialised mathematical notation without providing a few lines of explanations, as those that you wrote in your response, does not meet the standard of scholarship of the EMNLP conference. I recommend you fix this in the final version, if you have extra space. \n\nC: the new definition is ok.\n\nD: ok.\n\nE: you are right, sorry I misread steps (22) and (23).  You should be aware that the implementation of your deductive rule system should ensure that computation of weights w[j,Z,k] should be completed before undergoing steps (22) and (23). \n\nAccordingly, I have changed my overall score from 2 to 3. I wanted to provide 3.5, but this option is not available.", "paper_topic_and_main_contributions": "This draft considers the class of languages generated/recognized by tree-adjoining grammars or, equivalently, linear indexed grammars, pushdown-adjoining automata, and embedded pushdown automata. It is known that all of these formalisms can be viewed as two-level formalisms, where some controller formalism is used to control the derivations/computations of a second formalism, here called the controllee formalism. Using the combination of standard normal forms for both controller and controllee formalisms, and using dynamic programming techniques, the draft develops novel parsing algorithms for the weighted languages generated by tree-adjoining grammars.", "excitement": 3, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "Pop computations have been discussed a lot in the literature on dynamic programming techniques to simulate PDAs. I think you should add some references in Section 5. \n\n698: bib reference is incomplete, add name of the book.", "Typos_Grammar_Style_and_Presentation_Improvements": "097: say that each s_j is a token\n\n128: you define a sentential form as any string of nonterminal and terminal symbols.  This departs from the standard definition in formal language theory, where we require that such forms are derived starting from the initial symbol through the grammar productions. \n\n134: your definition of derivation is rather informal, why don't you use the rewrite relation => introduced in Def 4? Also, imposing that derivations end up with strings of terminal symbols only departs from the standard definition. Also, notice that you introduce derivation after sentential form, but it should be the other way around. \n\n150: configuration > configurations\n\n162: similarly to my comment on the definition of derivation, it is rather odd that you define configurations without imposing that they can be reached from the initial configuration through automaton transitions. \n\n164: contents > content\n\n184: your definition 9 is not used anywhere else in the draft, as far as I can see ... I wonder why you want to have a numbered definition for some notion that is never used. \n\nSection 3 introduces two-level formalisms without much discussion of the intuition behind the formalisms. I think this makes it very difficult for the reader to follow the developments of your findings. For instance, the intuition behind the tilde notation on rules is not presented. Same thing for the double dot notation that appears for the first time at l.230 and is used later on in your proofs. \n\n232-33: I do not understand string alpha' in rule p here, don't you need to use the double dot notation as at l.230-31? \n\nIn the draft you use the notation gamma[A], gamma a string of nonterminal/terminal symbols and A a nonterminal; see for instance l.236 and many other places in the same column/page. This notation is very ambiguous: it could be interpreted to mean that gamma ends with a nonterminal which is annotated with A, it could mean that every nonterminal in gamma is annotated with A (the intended interpretation, if I am not mistaken), etc. But I don't see any discussion of this notation in the running text of the draft. You should be very careful when using mathematical notation that is not standard. \n\n251: I think both occurrences of [S] here should instead use PDA initial configurations. \n\n264: p \\in d is an abuse of notation, since d is not a set.  You might want to use frequency notation: f(p,d) and place this at the exponent degree of \\pi, or else introduce a special convention for \\in. This is used throughout  the draft. \n\n286: G -> P, WLD-CFG -> WLD-PDA\n\n302: A run called accepting -> A run is called accepting\n\n346-49: I feel there are mistakes here with the indices ... \n\n447: eficiently -> efficiently\n\n456-57: to the weight of the subderivation d' -> to the weight of all subderivations having the form d' (?)\n\n471: here you define goal item on the basis of a PDA controller, but you said that the presentation will focus on CFG controller. \n\nProof of theorem 1: I don't really see the need for this proof, why don't you just say something like 'directly follows from the definition of item'?\n\nI have noticed that in the running text you never use references to your figures, why? One never really knows when to look into figures, this was a bit confusing to me especially with figure 2. \n\nrule (23) in figure 2: I think i,j should be j,k. \n\n530: rule (25) -> rule (24)"}}, {"review_id": "jFySx8LxHY", "reviewer": "Reviewer_1qtB", "summary": "", "questions": "A. As you note under Limitations (ll. 642-644), it \"add[s] extra complexity\" to transform a grammar into the equivalent two-level format and then convert it to the proposed normal form. How do these transformations impact grammar size in the worst case, and do you have results showing the actual impact on grammars that have been used in prior empirical work? Does the increased complexity ever outweigh the efficiency gains from your proposed parsing algorithm? (E.g. ll. 555-557 suggest that your approach somehow avoids the added factor of $|\\Gamma|$ in the space complexity, but is this not simply offloaded to the initial conversion so that you start from a larger grammar?)", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments and feedback! We greatly appreciate the time and effort put forth in order to understand our paper in detail and help us improve it. \n\n### A. As you note under Limitations (ll. 642-644), it \"add[s] extra complexity\" to transform a grammar into the equivalent two-level format and then convert it to the proposed normal form. How do these transformations impact grammar size in the worst case, and do you have results showing the actual impact on grammars that have been used in prior empirical work? Does the increased complexity ever outweigh the efficiency gains from your proposed parsing algorithm? (E.g. ll. 555-557 suggest that your approach somehow avoids the added factor of |Γ| in the space complexity, but is this not simply offloaded to the initial conversion so that you start from a larger grammar?)\n\nWe agree that we should discuss the extra complexity added by the conversions from TAG, LIG, EPDA, PAA into their corresponding 2-level formalisms and their conversions into their normal forms, and a comparison between the complexity of our algorithms (including the extra complexity added by these transformations) and the runtime of state-of-the-art algorithms. For instance, a full analysis of the complexity of our algorithm for a LIG, assuming that it has $|\\mathcal{N}|$ nonterminals and $|\\Gamma|$ stack symbols, would be:\n\n1. The controller PDA and the controllee CFG can be easily extracted in linear time from the rules of the LIG, resulting in a CFG with  $|\\mathcal{N}|$ nonterminals and a single-state PDA with $|\\Gamma|$ stack symbols.\n2. The controllee CFG needs to be converted into Chomsky normal form, and the controller PDA needs to be converted into the normal form. If the PDA has transitions that push at most k symbols, the resulting PDA has $\\mathcal{O}(k \\times |\\delta| \\times |Q|)$ states and $\\mathcal{O}(k \\times |\\delta|)$ transitions. \n3. Generally, the PDA conversion into the normal form will produce a PDA with multiple states, which needs to be converted back into a single-state PDA. If the PDA has $|Q|$ states and $|\\Gamma|$ stack symbols, the equivalent single-state PDA will have $\\mathcal{O}(|Q|^2 |\\Gamma|)$ stack symbols.\nThe rules of the controller and of the controllee can be merged back in linear time.\n\nHowever, the algorithm of Vijay-Shanker and Weir assumes an input LIG in a different normal form, which would be equivalent to a CFG in Chomsky normal form controlled by a simple PDA (Definition 9). So the conversion of a general LIG into such a form would also require similar transformations to ours, increasing the size of the original grammar. We would be happy to use some of the additional page to include such an analysis in the final version of the paper.\n\n### Consider adding parentheses when writing out PDA transitions, e.g. (p,X)→a/w(q,γ) on l. 169. Without parentheses, it reads at a glance like the transition is from X to q rather than from a tuple to another tuple. \n\nYou suggested adding brackets on both sides of a PDA transition, i.e., $(p, X) \\xrightarrow{a/w} (q, \\gamma)$. However, this might read as a move from a configuration to another configuration, which is inconsistent with our current definition of PDA configuration (a pair consisting of a state and the contents of the stack) since we only include the top of the stack in a transition. We will add brackets around the transitions instead so that they are separated better from the text surrounding them. \n\n### Ll. 255-256 seem to use different indexing in the equation vs the adjacent text: the equation suggests that p1 is the first production but the text suggests that it should be p0.\n\nIn Definition 12, lines 255-256, there is indeed an inconsistency in indexing. The first production of the derivation should be $p_1$ in line 255 and in line 256 there should be $\\alpha_{i-1} \\xRightarrow{p_i} \\alpha_i$ instead of $\\alpha_{i-1} \\xRightarrow{p_{i-1}} \\alpha_i$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This work describes a unified normal form for all of the common grammar formalisms that generate the class of tree-adjoining languages. Normal forms simplify the task of reasoning about a formalism, and having a unified normal form now trivializes the task of generalizing proofs from one of these formalisms to the others. A well-constructed normal form further simplifies the construction of efficient algorithms, as the authors demonstrate by developing a unified approach to parsing all of these formalisms. This parsing technique achieves state-of-the-art time-complexity, space-complexity, or both depending on the specific formalism under consideration. The authors also generalize the characterization of tree-adjoining formalisms in Butoi et al 2023 to include semiring-weighted variants, which are more practically applicable to NLP contexts where we are often interested in the likelihood of a given grammar producing some output.", "reasons_to_reject": "I do not see any compelling reasons to reject.", "questions_to_authors": "A. As you note under Limitations (ll. 642-644), it \"add[s] extra complexity\" to transform a grammar into the equivalent two-level format and then convert it to the proposed normal form. How do these transformations impact grammar size in the worst case, and do you have results showing the actual impact on grammars that have been used in prior empirical work? Does the increased complexity ever outweigh the efficiency gains from your proposed parsing algorithm? (E.g. ll. 555-557 suggest that your approach somehow avoids the added factor of $|\\Gamma|$ in the space complexity, but is this not simply offloaded to the initial conversion so that you start from a larger grammar?)", "paper_topic_and_main_contributions": "This paper builds on the new equivalencies between tree-adjoining grammars, linear indexed grammars, embedded pushdown automata, and pushdown adjoining automata recently proved in Butoi et al 2023. The authors exploit these equivalencies to construct a unified normal form for all of these formalisms, and to introduce semiring-weighted variants using the same \"control\" mechanism as Butoi et al. They use the unified normal form to develop a novel parsing algorithm which is suitable for the semiring-weighted versions of all four formalisms, and which improves on existing algorithms in terms of time complexity, space complexity, or both.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "Consider adding parentheses when writing out PDA transitions, e.g. $(p, X) \\xrightarrow{a/w} (q, \\gamma)$ on l. 169. Without parentheses, it reads at a glance like the transition is from X to q rather than from a tuple to another tuple. \n\nLl. 255-256 seem to use different indexing in the equation vs the adjacent text: the equation suggests that $p_1$ is the first production but the text suggests that it should be $p_0$.\n\nBuilding on my question A, it would be great to see the algorithm complexity stated in terms of the original grammar size (before conversion to a two-level CFG/PDA format) if possible, to clarify which aspects of the complexity derive from the transformation to the required form and which are from the parsing algorithm itself."}}, {"review_id": "S0NkKn0Se2", "reviewer": "Reviewer_VNxE", "summary": "", "questions": "none", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review! We greatly appreciate the time and effort put forth in order to understand our paper in detail and review it.\n\n\n### My main concern is whether the venue is suitable for this work, which is completely theoretical, without any empirical part in it, nor any discussion or example about potential applications.\n\nYou are correct that most papers published at *ACL conferences are not purely theoretical. However, we feel that research in formal language theory is still relevant to natural language. For instance, there have been many papers published at *ACL conferences that use similar formalisms for analyzing certain linguistic phenomena (e.g., cross-serial dependencies). Our paper focuses only on speeding up inference in these formalisms but it does not affect any of the results presented in these papers, therefore there is no need to revisit the empirical component. We agree that we should include some discussion about potential applications and we would be happy to do so in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "-- the quantities for which the computation is given are important for the application of the considered mechanisms\n\n-- the two level formalization gives an effective way of representing the formalism\n\n-- the proves seem correct to me", "reasons_to_reject": "None", "questions_to_authors": "none", "paper_topic_and_main_contributions": "This paper proposes a new algorithm to compute the probability of a string defined as the sum of the scores of all derivations of an input string and the total score of all derivations in the language for tree adjoining formalisms. The algorithm is based on a two-level representation including a controller and a controllee. Both can be either a context-free grammar (CFG) or a push-down automata (PDA).\n\nMain definitions necessary to understand the paper are included in the preliminaries section. The two level mechanism is then formally defined. On the basis of such definition, an extension of the Chomsky normal form is applied as a basis for following computations. The core of the paper consists on the computation of string sum and all sum, which is based on pop computations defined before. Correctness and complexity analysis are eventually proved. Strength and limitations of the approach are discussed. \n\nMy main concern was whether the venue is suitable for this work, which is completely theoretical, without any empirical part in it, nor any discussion or example about potential applications. After rebuttal, I think that if the authors add a discussion about potential applications, the problem can be solved.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "none", "Typos_Grammar_Style_and_Presentation_Improvements": "on line 447, eficiently -> efficiently"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a unified normal form for the class of tree-adjoining languages, the two-level representation leads to efficient algorithms to parse all those formalisms. Typically, they introduce new definitions of semiring-weighted two-level formalisms, propose new stringsum  and allsum algorithms, and prove the correctness and efficiency of their algorithms. Those formalisms and findings are beneficial to the community of tree-adjoining languages, and may lead to some potential applications.
Decision: Accept-Main