2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ PS. Feel free to re-tag... $\endgroup$ – Jukka Suomela Nov 17 '10 at 21:55
  • $\begingroup$ I think they arise naturally in parse trees for grammars, so it might be helpful to have a look there. $\endgroup$ – Kaveh Nov 19 '10 at 1:26

Your Answer

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

Browse other questions tagged or ask your own question.