<p>I need to specify small rooted trees with a lot of repeated parts and some recursive definitions.</p>

<p>To illustrate the need, let's use $s(T_1, T_2, ..., T_k)$ to denote a tree that consists of a degree-$k$ root node and $k$ subtrees: the $i$th subtree is a copy of $T_i$. Then I might want to define something like this:</p>

<ul>
<li>$T = s(X_d, X_d, X_d, B)$
<ul>
<li>$X_{i+1} = s(X_i, X_i, X_i, X_i)$
</li>
<li>$X_0 = s(A, B, B)$
</li>
<li>$A = s(C, D, D)$
</li>
<li>$B = s(D, D, D)$
</li>
<li>$C = s(L, L, L)$
</li>
<li>$D = s(L, L)$
</li>
<li>$L =$ a leaf node</li>
</ul></li>
</ul>

<p>Well, certainly I can define it, but I would prefer to <em>draw</em> an illustration that defines the structure of $T$. I would prefer to keep the illustration as compact as possible, yet unambiguous (that is, the illustration alone is enough to <em>define</em> $T$). I would rather not name the subtrees $X_i$, $A$, $B$, ...; they could be just some anonymous nodes (?) in the illustration.</p>

<p>Sure, I could come up with my own notation for such illustrations, but when I tried to depict recursion I realised that using a well-known standard notation might be a better idea. Hence the question:</p>

<blockquote>
  <p>What is the standard notation for drawing trees that contain recursive parts and isomorphic subtrees?</p>
</blockquote>

<p>I explored ideas ranging from the Unified Modeling Language to tree grammars, but did not find anything that really answers my needs. Any ideas? Preferably something that might be already familiar to a computer scientist.</p>

CC BY-SA 2.5
2010-11-17T21:55:55.613Z
PS. Feel free to re-tag...
Jukka Suomela
CC BY-SA 2.5
2010-11-19T01:26:45.727Z
I think they arise naturally in parse trees for grammars, so it might be helpful to have a look there.
Kaveh
<graph-theory><tree>
Notation for drawing rooted trees with isomorphic subtrees and recursive parts
Jukka Suomela
# Notation for drawing rooted trees with isomorphic subtrees and recursive parts

(Asked by: username_0 on 2010-11-17)

I need to specify small rooted trees with a lot of repeated parts and some recursive definitions.

To illustrate the need, let's use $s(T\_1, T\_2, ..., T\_k)$ to denote a tree that consists of a degree-$k$ root node and $k$ subtrees: the $i$th subtree is a copy of $T\_i$. Then I might want to define something like this:

* $T = s(X\_d, X\_d, X\_d, B)$
  + $X\_{i+1} = s(X\_i, X\_i, X\_i, X\_i)$
  + $X\_0 = s(A, B, B)$
  + $A = s(C, D, D)$
  + $B = s(D, D, D)$
  + $C = s(L, L, L)$
  + $D = s(L, L)$
  + $L =$ a leaf node

Well, certainly I can define it, but I would prefer to *draw* an illustration that defines the structure of $T$. I would prefer to keep the illustration as compact as possible, yet unambiguous (that is, the illustration alone is enough to *define* $T$). I would rather not name the subtrees $X\_i$, $A$, $B$, ...; they could be just some anonymous nodes (?) in the illustration.

Sure, I could come up with my own notation for such illustrations, but when I tried to depict recursion I realised that using a well-known standard notation might be a better idea. Hence the question:

> What is the standard notation for drawing trees that contain recursive parts and isomorphic subtrees?

I explored ideas ranging from the Unified Modeling Language to tree grammars, but did not find anything that really answers my needs. Any ideas? Preferably something that might be already familiar to a computer scientist.

**Tags:** graph-theory, tree

> **Comments:**
> **username_0**: PS. Feel free to re-tag...  
> **username_1**: I think they arise naturally in parse trees for grammars, so it might be helpful to have a look there.  

---

## 0 answers

