The Relation Between Tree-Adjoining Grammars and Constraint Dependency Grammars

For the two grammar formalisms Tree--Adjoining Grammars (TAGs) and Constraint Dependency Grammars (CDGs), it is known that they are mildly context--sensitive. In both formalisms, natural--language phenomena can appropriately be specified. TAGs provide an adequate domain of locality by defining trees as rules. In a CDG, more or less strictly formulated local constraints are written which must be satisfiable all over the system. For both, polynomial parsers have been proposed in the literature (O(n 4 ) for CDGs and O(n 5 ) for TAGs). Consequently, it seems reasonable to compare the two formalisms in more detail because each provides convincing features to the grammar writer. In the following paper, we show that each TAG can be transformed into an equivalent CDG but not vice versa. This is shown by outlining how a CDG produces the non Tree--Adjoining language L--6 := a n b n c n d n e n f n