Multiple context-free grammars

TAG uses the two sides of one foot node to represent a gap. How can we represent discontinuity directly? Multiple context-free grammars (MCFGs) allow a nonterminal to derive a tuple of strings (Seki et al. 1991). Other material may occur between those components in the final yield.

Linear context-free rewriting systems (LCFRSs) provide a closely related notation (Vijay-Shanker et al. 1987). The two formalisms have the same weak generative capacity under their standard definitions, so we will use MCFG notation while drawing the parsing rules from the LCFRS literature.

Reading

Read Kallmeyer (2013) through the recognition rules for binary LCFRS.

Fan-out

Each nonterminal $A$ has a positive integer fan-out, written $\operatorname{fo}(A)$. This is the number of string components in a value derived by $A$.

A fan-out-one nonterminal derives one contiguous string.
A fan-out-two nonterminal derives a pair of strings.

The start symbol has fan-out one because a complete derivation must produce one string.

An MCFG rule combines the components derived by its right-hand-side nonterminals using a tuple-valued function. Under the usual linear and nonerasing restrictions, each input variable occurs exactly once in the output tuple. Linearity prevents copying; nonerasure prevents deletion.

A copying language

Consider the language

\[L_{copy} = \{ww \mid w\in\{a,b\}^*\}.\]

It is not context-free, but a fan-out-two MCFG can generate it:

\[ \begin{aligned} A(\epsilon,\epsilon) &\leftarrow \epsilon \\ A(ax,ay) &\leftarrow A(x,y) \\ A(bx,by) &\leftarrow A(x,y) \\ S(xy) &\leftarrow A(x,y). \end{aligned} \]

The two components of $A$ grow in parallel. The start rule concatenates them, producing two identical copies of the selected string.

We prove this claim using double inclusion, just as we did for CFG closure. First, every tuple derived by $A$ has the form $(w,w)$. The base rule derives $(\epsilon,\epsilon)$. If the invariant holds of $(x,y)$, the $a$ rule derives $(ax,ay)$ and the $b$ rule derives $(bx,by)$. Since $x=y$, the two new components are again identical. Induction on derivation height proves that the start rule can produce only strings $ww$.

Conversely, fix any $w\in\{a,b\}^*$. We induct on its length. The empty string is supplied by the base rule. If $w=cv$ for $c\in\{a,b\}$, the induction hypothesis derives $A(v,v)$. Use the $a$ rule when $c=a$ or the $b$ rule when $c=b$ to derive $A(cv,cv)=A(w,w)$. The start rule then derives $ww$. Thus, the grammar generates all and only $L_{copy}$.

Question

Why does this grammar require fan-out two?

Answer

The derivation must keep the two copies separate while extending them in parallel. A fan-out-one nonterminal supplies only one contiguous component; under the MCFG definition, fan-out-one grammars generate exactly the context-free languages.

Recognition items

A recognition item for fan-out-$m$ nonterminal $A$ has the form

\[ [A; (i_1,j_1),\ldots,(i_m,j_m)]. \]

It asserts that the $r$th component of $A$ covers the half-open span $(i_r,j_r)$. An inference rule combines antecedent items when their spans satisfy the concatenation pattern specified by an MCFG rule. The goal item for an input of length $n$ is $[S;(0,n)]$.

This is the same deductive architecture used for CKY. The difference lies in the item shape and in the compatibility conditions over tuples of spans.

For every fixed MCFG, recognition is polynomial in the input length. The exponent depends on properties of the grammar, including its fan-out and rule rank; $O(n^{3f})$ is thus not a general complexity formula for every grammar of fan-out $f$.

The polynomial bound follows from fixing the grammar before varying the input. A fan-out-$m$ item contains $2m$ endpoints, and each endpoint has at most $n+1$ values. Thus, one nonterminal has at most $(n+1)^{2m}$ possible span tuples. The grammar contains finitely many nonterminals, has a fixed maximum fan-out, and gives each inference rule a fixed number of endpoint variables. Enumerating every assignment to the variables of one fixed rule thus takes $O(n^c)$ time for some constant $c$ determined by that rule. Saturating the finite item set under the finite rule set remains polynomial in $n$.

This argument does not supply one exponent for all MCFGs. Changing the grammar may change the maximum fan-out, rule rank, and number of independent endpoints, and hence changes $c$.

Relative generative capacity

The first levels of the fan-out hierarchy should not be conflated:

\[ \text{CFG}=\text{MCFG}(1) \subsetneq \text{TAG languages} \subsetneq \text{MCFG}. \]

TAG languages can be represented by constrained fan-out-two LCFRSs or MCFGs. Unrestricted fan-out-two grammars already include languages outside the TAG class, and allowing larger fan-out yields further increases in capacity.

The equalities and containments in this section require translations, not merely example languages. The equivalence proofs construct the relevant grammars in both directions and prove their yield invariants step by step.

The final project asks you to implement an MCFG recognizer. Its rule objects encode the same tuple-concatenation functions described here; its chart items encode tuples of input spans.

References

Kallmeyer, Laura. 2013. “Linear Context-Free Rewriting Systems.” Language and Linguistics Compass 7 (1): 22–38. https://doi.org/10.1002/lnc3.359.

Seki, Hiroyuki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. “On Multiple Context-Free Grammars.” Theoretical Computer Science 88 (2): 191–229. https://doi.org/10.1016/0304-3975(91)90374-B.

Vijay-Shanker, K., David J. Weir, and Aravind K. Joshi. 1987. “Characterizing Structural Descriptions Produced by Various Grammatical Formalisms.” Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics, 104–11.

--- title: Multiple context-free grammars bibliography: ../../references.bib --- TAG uses the two sides of one foot node to represent a gap. How can we represent discontinuity directly? Multiple context-free grammars (MCFGs) allow a nonterminal to derive a tuple of strings [@seki1991multiple]. Other material may occur between those components in the final yield. Linear context-free rewriting systems (LCFRSs) provide a closely related notation [@vijayshanker1987characterizing]. The two formalisms have the same weak generative capacity under their standard definitions, so we will use MCFG notation while drawing the parsing rules from the LCFRS literature. ::: {.callout-note title="Reading"} Read @kallmeyer_linear_2013 through the recognition rules for binary LCFRS. ::: ## Fan-out Each nonterminal $A$ has a positive integer *fan-out*, written $\operatorname{fo}(A)$. This is the number of string components in a value derived by $A$. - A fan-out-one nonterminal derives one contiguous string. - A fan-out-two nonterminal derives a pair of strings. The start symbol has fan-out one because a complete derivation must produce one string. An MCFG rule combines the components derived by its right-hand-side nonterminals using a tuple-valued function. Under the usual *linear* and *nonerasing* restrictions, each input variable occurs exactly once in the output tuple. Linearity prevents copying; nonerasure prevents deletion. ## A copying language Consider the language $$L_{copy} = \{ww \mid w\in\{a,b\}^*\}.$$ It is not context-free, but a fan-out-two MCFG can generate it: $$ \begin{aligned} A(\epsilon,\epsilon) &\leftarrow \epsilon \\ A(ax,ay) &\leftarrow A(x,y) \\ A(bx,by) &\leftarrow A(x,y) \\ S(xy) &\leftarrow A(x,y). \end{aligned} $$ The two components of $A$ grow in parallel. The start rule concatenates them, producing two identical copies of the selected string. We prove this claim using [double inclusion](../../languages-as-formal-objects/set-relations.qmd#equality-by-double-inclusion), just as we did for [CFG closure](../../morphological-patterns/operations.qmd#why-the-constructions-work). First, every tuple derived by $A$ has the form $(w,w)$. The base rule derives $(\epsilon,\epsilon)$. If the invariant holds of $(x,y)$, the $a$ rule derives $(ax,ay)$ and the $b$ rule derives $(bx,by)$. Since $x=y$, the two new components are again identical. Induction on derivation height proves that the start rule can produce only strings $ww$. Conversely, fix any $w\in\{a,b\}^*$. We induct on its length. The empty string is supplied by the base rule. If $w=cv$ for $c\in\{a,b\}$, the induction hypothesis derives $A(v,v)$. Use the $a$ rule when $c=a$ or the $b$ rule when $c=b$ to derive $A(cv,cv)=A(w,w)$. The start rule then derives $ww$. Thus, the grammar generates all and only $L_{copy}$. ::: {.callout-note collapse="true" title="Question"} Why does this grammar require fan-out two? ::: {.callout-tip collapse="true" title="Answer"} The derivation must keep the two copies separate while extending them in parallel. A fan-out-one nonterminal supplies only one contiguous component; under the MCFG definition, fan-out-one grammars generate exactly the context-free languages. ::: ::: ## Recognition items A recognition item for fan-out-$m$ nonterminal $A$ has the form $$ [A; (i_1,j_1),\ldots,(i_m,j_m)]. $$ It asserts that the $r$th component of $A$ covers the half-open span $(i_r,j_r)$. An inference rule combines antecedent items when their spans satisfy the concatenation pattern specified by an MCFG rule. The goal item for an input of length $n$ is $[S;(0,n)]$. This is the same deductive architecture used for CKY. The difference lies in the item shape and in the compatibility conditions over tuples of spans. For every fixed MCFG, recognition is polynomial in the input length. The exponent depends on properties of the grammar, including its fan-out and rule rank; $O(n^{3f})$ is thus not a general complexity formula for every grammar of fan-out $f$. The polynomial bound follows from fixing the grammar before varying the input. A fan-out-$m$ item contains $2m$ endpoints, and each endpoint has at most $n+1$ values. Thus, one nonterminal has at most $(n+1)^{2m}$ possible span tuples. The grammar contains finitely many nonterminals, has a fixed maximum fan-out, and gives each inference rule a fixed number of endpoint variables. Enumerating every assignment to the variables of one fixed rule thus takes $O(n^c)$ time for some constant $c$ determined by that rule. Saturating the finite item set under the finite rule set remains polynomial in $n$. This argument does not supply one exponent for all MCFGs. Changing the grammar may change the maximum fan-out, rule rank, and number of independent endpoints, and hence changes $c$. ## Relative generative capacity The first levels of the fan-out hierarchy should not be conflated: $$ \text{CFG}=\text{MCFG}(1) \subsetneq \text{TAG languages} \subsetneq \text{MCFG}. $$ TAG languages can be represented by constrained fan-out-two LCFRSs or MCFGs. Unrestricted fan-out-two grammars already include languages outside the TAG class, and allowing larger fan-out yields further increases in capacity. The equalities and containments in this section require translations, not merely example languages. The [equivalence proofs](proving-equivalences.qmd) construct the relevant grammars in both directions and prove their yield invariants step by step. The [final project](../../assignments/final-project.ipynb) asks you to implement an MCFG recognizer. Its rule objects encode the same tuple-concatenation functions described here; its chart items encode tuples of input spans.