📄 Characterizing Structural Descriptions Produced by Various Grammatical Formalisms

Summary

Most comparisons of grammar formalisms look only at the string languages they generate (weak generative capacity). This paper looks instead at the trees they assign (strong generative capacity). It compares CFG's, Head Grammars, Tree Adjoining Grammars, Categorial Grammars, Indexed Grammars, LFG and multicomponent TAG's on two properties. The first is how complex the root-to-frontier path sets of their trees are. The second is whether separate paths can depend on one another. The authors set aside the specific data structures and combining operations and examine derivation trees. Seen this way, CFG's, HG's, TAG's and MCTAG's all have derivation tree sets with the same shape as local sets, the tree sets of CFG's. Generalizing this shared context-freeness, they sketch a family called Linear Context-Free Rewriting Systems (LCFRS). Its composition operations must be linear and nonerasing. They show that every member generates semilinear languages, which gives the constant growth property, and can be recognized in polynomial time. This offers a candidate formal account of mild context-sensitivity.

Key points

• Path complexity differs across formalisms.
  • CFG trees have regular path sets, which follows from Thatcher (1973). CFG's therefore cannot build trees with nested dependencies along a spine, such as Gazdar's Norwedish analysis.
  • TAG path sets are context-free.
  • IG path sets are also context-free, following Rounds (1969).
• Path dependence separates IG's and LFG from the rest. IG's (through stack sharing) and LFG/FUG (through unification) can make two unboundedly long branches depend on each other, for example by forcing them to have equal length. CFG's, HG's and TAG's cannot do this.
• Unrestricted composition in Categorial Grammars also creates dependent paths. Steedman's general composition yields dependent branches and a language that neither TAG's nor HG's can generate. With a restricted form of composition, the paths become independent. Whether that restricted CG is equivalent to TAG's and HG's is left open.
• MCTAG's sit in between. They allow a bounded number of dependent paths while keeping local-set derivation trees. Polynomial-time recognition of MCTAG's follows as a corollary of the LCFRS result.
• LCFRS recognition and notation. The polynomial recognition result requires each derived structure to span a bounded number of possibly non-adjacent substrings, combined by concatenation. LCFRS notation is deliberately narrower than Rounds' ILFP.

Interesting ideas

• I1. Compare systems through their derivation trees. Comparing the history of how structures are built, rather than the surface operations, can reveal that very different-looking systems are the same kind of thing. This lens could be reused to compare parsers or generation pipelines.
• I2. Use two independent measures of tree sets. Path complexity and independence between paths are separate yardsticks. They could serve as diagnostics for how expressive any tree-producing model is, such as treebank annotation schemes or neural parsers.
• I3. Constrain the operations, not the objects. Requiring combining operations to be linear and nonerasing (never copying or deleting material) is a clean design restriction. It keeps a system efficient even when the objects it manipulates are richer than strings.
• I4. Represent constituents as bounded tuples of substrings. Letting each constituent cover a bounded number of discontinuous substrings explains why polynomial-time parsing stays possible. This is useful for handling discontinuous or non-projective structures, which matter for free word-order languages such as Ukrainian.
• I5. Separate dependency within a branch from dependency between branches. The paper suggests that limiting how much information sibling subderivations share is what drives tractability. This helps when deciding how much cross-branch communication a model or grammar should allow.