Strong Equivalence of TAG and CCG
Open Access
- 2 August 2021
- journal article
- research article
- Published by MIT Press in Transactions of the Association for Computational Linguistics
- Vol. 9, 707-720
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.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Impartiality and Anticipation for Monitoring of Visibly Context-Free PropertiesLecture Notes in Computer Science, 2013
- Tree-Adjoining Grammars Are Not Closed Under Strong LexicalizationComputational Linguistics, 2012
- The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree GrammarsJournal of Logic, Language and Information, 2011
- Combinatory Categorial Grammar2011
- Spinal-Formed Context-Free Tree GrammarsTheory of Computing Systems, 2000
- Tree Languages1997
- Context-Free Languages and Pushdown Automata1997
- The equivalence of four extensions of context-free grammarsTheory of Computing Systems, 1994
- Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?1985
- On the equivalence of mealy-type and moore-type automata and a relation between reducibility and moore-reducibilityJournal of Computer and System Sciences, 1977