We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold close resemblances to the well-known string analogues.

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

Obviously there are tree languages such that the height of a tree is linear in its size; and in the book Analytic Combinatorics it is shown e.g. that binary trees of size $n$ have average height $2\sqrt{ \pi n}$. If I understand Proposition VII.16 (p.537) of the mentioned book correctly, then there is a wide subset of regular tree languages that have average height of $\Theta(\sqrt{n})$, namely those in which the tree language is also a simple variety of trees fulfilling some extra conditions.

So I was wondering whether there is a regular tree language showing a different average height or if there is a true dichotomy for regular tree languages.

  • 4
    $\begingroup$ What exactly do you mean by "regular tree language"; such generated by regular tree grammars resp. tree automata? How do these relate to simple trees as Flajolet/Sedgewick talk about? From my understanding, tree grammars fit the combinatoric framework (in particular, they do not rely on data as e.g. tries do) so general results should carry over. $\endgroup$ – Raphael Oct 17 '13 at 14:48
  • 4
    $\begingroup$ By "regular tree language" I mean exactly what you said, i.e. the definition from the book TATA. The simple trees they talk about are a subclass of regular trees. An example regular tree class that does not belong to Flajolet's setting is the class of binary trees in which only the right-most branch may have unary nodes (I wasn't able to calculate those trees' average height so far). $\endgroup$ – john_leo Oct 17 '13 at 20:42
  • 4
    $\begingroup$ Note that the question has been reposted on cstheory.SE. Let's hope they find an answer over there! $\endgroup$ – Raphael Jan 19 '14 at 14:45
  • $\begingroup$ For those who stumble over this question: john_leo and me actually worked on this for a while in 2014; find a summary here. $\endgroup$ – Raphael Oct 14 '18 at 14:10

protected by Community Jun 24 at 12:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Browse other questions tagged or ask your own question.