As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar hierarchy?

By the tree grammar hierarchy I mean one which is similar to the Chomsky hierarchy of word grammars, e.g. as on this figure taken from

Matsuda K., Mu SC., Hu Z., Takeichi M. (2010) A Grammar-Based Approach to Invertible Programs. In: Gordon A.D. (eds) Programming Languages and Systems. ESOP 2010. Lecture Notes in Computer Science, vol 6012. Springer, Berlin, Heidelberg

enter image description here

  • 2
    $\begingroup$ They are "essentially" linear monadic context-free tree grammars. Monadic means that nonterminals have arity at most one. Being linear entails that IO vs. OI is irrelevant. "Essentially" means that they are (in their basic definition) somewhat "local", just like the derivation trees of context-free word grammars are local and do not quite generate all the regular tree languages. $\endgroup$ – Sylvain Apr 1 '17 at 18:03
  • $\begingroup$ Wow, so this class is somewhat intersecting with RTG and lying inside CFTG? Are any papers covering this topic? $\endgroup$ – Andrey Lebedev Apr 1 '17 at 19:14
  • $\begingroup$ I don't think anyone tried to pinpoint TAG tree languages exactly; the equivalence with linear monadic context-free tree grammars when one slightly extends the definition is on the other hand folklore. $\endgroup$ – Sylvain Apr 1 '17 at 20:55

Actually I've found the answer. Here is quote from unpublished work (lecture notes?) of M. Kanazawa:

The class of tree languages of tree-adjoining grammars is included in the class of tree languages generated by monadic simple context-free tree grammars.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.