Strong Equivalence of TAG and CCG
This resolves a foundational theoretical question in computational linguistics about the equivalence of two key grammar formalisms, confirming their expressive alignment in tree structures.
The paper demonstrates that Tree-Adjoining Grammar (TAG) and Combinatory Categorial Grammar (CCG) have essentially the same expressive power on trees, not just strings, showing that CCG with restrictions (no empty string lexicon entries and only first-order rules of degree at most 2) achieves this full power.
Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are two well-established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demonstrated that their expressive power on trees also essentially coincides. In fact, CCG without lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power.