<p>Actually I've found the answer. Here is quote from <a href="https://pdfs.semanticscholar.org/95a3/cb63b80c3416879d534f41eedcd174b40159.pdf" rel="nofollow noreferrer">unpublished work</a> (lecture notes?) of M. Kanazawa:</p>

<blockquote>
  <p>The class of tree languages of <strong>tree-adjoining grammars</strong> is included in
  the class of tree languages generated by monadic simple context-free
  tree grammars.</p>
</blockquote>

CC BY-SA 3.0
2017-04-02T20:00:16.680Z
2017-04-02T20:00:16.680Z
Andrey Lebedev
<p>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? </p>

<p>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 </p>

<blockquote>
  <p>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</p>
</blockquote>

<p><a href="https://i.sstatic.net/o2SRH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/o2SRH.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-04-01T18:03:54.053Z
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.
Sylvain
CC BY-SA 3.0
2017-04-01T19:14:05.337Z
Wow, so this class is somewhat intersecting with RTG and lying inside CFTG? Are any papers covering this topic?
Andrey Lebedev
CC BY-SA 3.0
2017-04-01T20:55:42.457Z
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.
Sylvain
<fl.formal-languages><tree><grammars>
Place of tree-adjoining grammars in the hierarchy of tree grammars
Andrey Lebedev
# Place of tree-adjoining grammars in the hierarchy of tree grammars

(Asked by: username_0 on 2017-04-01)

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](https://i.sstatic.net/o2SRH.png)](https://i.sstatic.net/o2SRH.png)

**Tags:** fl.formal-languages, tree, grammars
> **Comments:**
> **username_1**: 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.  
> **username_0**: Wow, so this class is somewhat intersecting with RTG and lying inside CFTG? Are any papers covering this topic?  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2017-04-02. Score: 2

Actually I've found the answer. Here is quote from [unpublished work](https://pdfs.semanticscholar.org/95a3/cb63b80c3416879d534f41eedcd174b40159.pdf) (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.


---

