# 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})$?

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.

Note: This question has been asked before on Computer Science, yet it has been unanswered for more than three months. I would like to repost it here because the question is too old to migrate and because there is still an interest in the question. Here is a link to the original post.

• The single tree with constant depth is an obvious answer: o(\sqrt{n}) but not $\Omega(\sqrt{n})$. I believe you probably meant some other question? Replace $\Theta(\sqrt{n})$ with $O(\sqrt{n})$ maybe? – Joseph Stack Jan 19 '14 at 13:30
• Yes and no. I think a regular tree language with average depth $O(n^{1/3})$ (say) would also be very interesting. But you're right in that we should exclude such degenerated cases. Maybe we should require that the tree language contains infinitely many elements? – john_leo Jan 19 '14 at 13:39
• What kind of trees do you have in mind? Ranked trees, unranked sibling-ordered trees, unranked unordered trees; and, by the way, what kind of tree automata do you mean, bottom-up or top-down? – f-h Jan 19 '14 at 13:46
• @JosephStack how can the height of a regular tree be infinite? A tree with $n$ nodes cannot have a height greater than $n$. – john_leo Jan 19 '14 at 13:50
• @Raphael: If you do not consider $\lim\sup$, it's not clear to me what the question would be. The answer to "is there an infinite regular tree language such that the mean height is a function $f$ with $f(n)\notin \Theta(\sqrt{n})$ and $f(n)\notin\Theta(n)$" is obviously yes: make sure that for odd $n$ you have $\Theta(n)$ and even ones $\Theta(\sqrt{n})$. P.S. every function I can imagine belongs to $\Theta(g)$ for some $g\notin\{\sqrt{n},n\}$, so it's not a correct fix :) – Joseph Stack Jan 19 '14 at 15:10

I believe that the answer is as you suggest that no other asymptotics than $\Theta(1)$, $\Theta(\sqrt{n})$ and $\Theta(n)$ are possible. A promising route to prove this could be to apply the techniques from the paper which derives the $\Theta(\sqrt{n})$ asymptotics to the run trees of the regular language. Notice that a tree is accepted if there exists a run tree so it should be possible to first derive (using loc.cit.) the average height of a randomly generated run tree and take it from there, i.e. show that projecting away the states does not change the average height.