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

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.

• 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. Commented Oct 17, 2013 at 14:48
• 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). Commented Oct 17, 2013 at 20:42
• Note that the question has been reposted on cstheory.SE. Let's hope they find an answer over there! Commented Jan 19, 2014 at 14:45
• For those who stumble over this question: john_leo and me actually worked on this for a while in 2014; find a summary here. Commented Oct 14, 2018 at 14:10
• I’m voting to close this question because it was cross-posted. I suggest posting any answers over on TCS.SE.
– D.W.
Commented Dec 23, 2022 at 23:57