Strong Equivalence of TAG and CCG

Lena Katharina Schiffer, Andreas Maletti


Abstract
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.
Anthology ID:
2021.tacl-1.43
Volume:
Transactions of the Association for Computational Linguistics, Volume 9
Month:
Year:
2021
Address:
Cambridge, MA
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
707–720
Language:
URL:
https://aclanthology.org/2021.tacl-1.43
DOI:
10.1162/tacl_a_00393
Bibkey:
Cite (ACL):
Lena Katharina Schiffer and Andreas Maletti. 2021. Strong Equivalence of TAG and CCG. Transactions of the Association for Computational Linguistics, 9:707–720.
Cite (Informal):
Strong Equivalence of TAG and CCG (Schiffer & Maletti, TACL 2021)
Copy Citation:
PDF:
https://aclanthology.org/2021.tacl-1.43.pdf