<p>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 <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf" rel="nofollow noreferrer">the paper which derives the $\Theta(\sqrt{n})$ asymptotics</a> 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 <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf" rel="nofollow noreferrer">loc.cit.</a>) 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. </p>

CC BY-SA 3.0
2017-10-18T11:19:13.023Z
I think this is a comment and not an answer since it is far from clear wether this attempt works out.
Danny
CC BY-SA 3.0
2017-10-12T12:01:22.047Z
2017-10-12T12:01:22.047Z
Martin Hofmann
<p>We define a <em>regular tree language</em> as in the book <a href="http://tata.gforge.inria.fr/" rel="noreferrer">TATA</a>: 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.</p>

<blockquote>
  <p>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})$?</p>
</blockquote>

<p>Obviously there are tree languages such that the height of a tree is linear in its size; and in the book <a href="http://algo.inria.fr/flajolet/Publications/books.html" rel="noreferrer">Analytic Combinatorics</a> 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 <em>simple variety of trees</em> fulfilling some extra conditions.</p>

<p>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.</p>

<p>Note: This question has been asked before on <a href="https://cs.stackexchange.com/">Computer Science</a>, 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 <a href="https://cs.stackexchange.com/questions/16073/is-there-a-regular-tree-language-in-which-the-average-height-of-a-tree-of-size">link</a> to the original post.</p>

CC BY-SA 3.0
2014-01-19T13:30:40.000Z
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
CC BY-SA 3.0
2014-01-19T13:39:25.887Z
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
CC BY-SA 3.0
2014-01-19T13:46:45.193Z
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
CC BY-SA 3.0
2014-01-19T13:50:48.753Z
@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
CC BY-SA 3.0
2014-01-19T13:51:29.283Z
Of course you're right; height is finite. I was trying to delete that 'stupid' comment of mine but did not manage, sorry
Joseph Stack
CC BY-SA 3.0
2014-01-19T13:58:59.063Z
@f-h just as defined in Tata, chapter 1/2. So ranked trees. I mean bottom-up tree automata.
john_leo
CC BY-SA 3.0
2014-01-19T14:28:41.507Z
I believe the "limit" is not well defined in terms of $\Theta$. Because you could extract two infinite subsequences of $n$ for which the average height radically differs. Are you interested in $\lim \sup$ of the average height?
Joseph Stack
CC BY-SA 3.0
2014-01-19T14:41:41.283Z
@JosephStack: Asymptotics don't make sense on finite classes (that is, the limit is $0$ on all finite classes), so the question already requires an infinite class of trees. The term "regular tree language" has clear definitions (see the cited references) and the average tree height is canonically defined as the mean height of all trees with $n$ nodes that are in the language. Therefore, the question is quite unambiguous.
Raphael
CC BY-SA 3.0
2014-01-19T14:50:01.050Z
@JosephStack My bad, the question does not explicitly ask for a class with mean height in $\Theta(g)$ for $g \not\in \{\sqrt{n}, n\}$.
Raphael
CC BY-SA 3.0
2014-01-19T15:10:19.747Z
@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
CC BY-SA 3.0
2014-01-19T15:18:00.237Z
@JosephStack Why consider any limits? $\Theta$ is not typically defined via $\lim$; if anything, $\lim\sup$ is used and your concern is gone. Note that your "..." are not equivalent to what I wrote. (I should have added that in my phrasing, we'd like $g \in \omega(1)$ and probably stricly increasing so nasty corner cases go away.)
Raphael
CC BY-SA 3.0
2014-01-20T11:55:06.247Z
Maybe you could just state that you ask whether for every $L$ there is a $c$ and $C$ such that for every $n$ the average depth of size $n$ trees is either at most $C$ or between $c\sqrt n$ and $C\sqrt n$ or at least $cn$. Btw, I think this could be true and if I were you, I would rather ask it on mathoverflow.
domotorp
CC BY-SA 3.0
2014-01-20T12:10:58.863Z
@domotorp What would that reformulation change? Btw, I also believe it's true. And I was also thinking about asking it on mathoverflow, since the answer of the question surely involves many analytic tools...
john_leo
CC BY-SA 3.0
2014-01-20T15:05:12.037Z
I think half of the above comments are related to people being confused about the exact meaning of your question, so it would change that.
domotorp
CC BY-SA 3.0
2015-02-10T22:15:28.627Z
fyi the question seemed not exactly precise over on [cs.se](http://cs.stackexchange.com/questions/16073/is-there-a-regular-tree-language-in-which-the-average-height-of-a-tree-of-size) awhile back either but was high voted also & still stumped the crowd. maybe some more clarification of bkg/ definitions to make it _self contained_ (as possible) esp wrt math formulations instead of mere citations would help. also presumably the book does not say anything about a _dichotomy_ & that is your own term? no _dichotomy_ seems to be apparent/ clearly defined...
vzn
CC BY-SA 4.0
2018-10-14T14:26:24.937Z
For those who stumble over this question: john_leo and me actually worked on this for a while in 2014; find a summary [here](http://reitzig.github.io/research/open-questions/#average-height-of-regular-trees).
Raphael
<co.combinatorics><fl.formal-languages><tree><regular-language>
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})$?
john_leo
# 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})$?

(Asked by: username_0 on 2014-01-19)

We define a *regular tree language* as in the book [TATA](http://tata.gforge.inria.fr/): 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](http://algo.inria.fr/flajolet/Publications/books.html) 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](https://cs.stackexchange.com/), 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](https://cs.stackexchange.com/questions/16073/is-there-a-regular-tree-language-in-which-the-average-height-of-a-tree-of-size) to the original post.

**Tags:** co.combinatorics, fl.formal-languages, tree, regular-language
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_2**: 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?  
> **username_0**: @JosephStack how can the height of a regular tree be infinite? A tree with $n$ nodes cannot have a height greater than $n$.  
> **username_1**: Of course you're right; height is finite. I was trying to delete that 'stupid' comment of mine but did not manage, sorry  
> **username_0**: @f-h just as defined in Tata, chapter 1/2. So ranked trees. I mean bottom-up tree automata.  
> **username_1**: I believe the "limit" is not well defined in terms of $\Theta$. Because you could extract two infinite subsequences of $n$ for which the average height radically differs. Are you interested in $\lim \sup$ of the average height?  
> **username_3**: @JosephStack: Asymptotics don't make sense on finite classes (that is, the limit is $0$ on all finite classes), so the question already requires an infinite class of trees. The term "regular tree language" has clear definitions (see the cited references) and the average tree height is canonically defined as the mean height of all trees with $n$ nodes that are in the language. Therefore, the question is quite unambiguous.  
> **username_3**: @JosephStack My bad, the question does not explicitly ask for a class with mean height in $\Theta(g)$ for $g \not\in \{\sqrt{n}, n\}$.  
> **username_1**: @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 :)  
> **username_3**: @JosephStack Why consider any limits? $\Theta$ is not typically defined via $\lim$; if anything, $\lim\sup$ is used and your concern is gone. Note that your "..." are not equivalent to what I wrote. (I should have added that in my phrasing, we'd like $g \in \omega(1)$ and probably stricly increasing so nasty corner cases go away.)  
> **username_4**: Maybe you could just state that you ask whether for every $L$ there is a $c$ and $C$ such that for every $n$ the average depth of size $n$ trees is either at most $C$ or between $c\sqrt n$ and $C\sqrt n$ or at least $cn$. Btw, I think this could be true and if I were you, I would rather ask it on mathoverflow.  
> **username_0**: @domotorp What would that reformulation change? Btw, I also believe it's true. And I was also thinking about asking it on mathoverflow, since the answer of the question surely involves many analytic tools...  
> **username_4**: I think half of the above comments are related to people being confused about the exact meaning of your question, so it would change that.  
> **username_5**: fyi the question seemed not exactly precise over on [cs.se](http://cs.stackexchange.com/questions/16073/is-there-a-regular-tree-language-in-which-the-average-height-of-a-tree-of-size) awhile back either but was high voted also & still stumped the crowd. maybe some more clarification of bkg/ definitions to make it _self contained_ (as possible) esp wrt math formulations instead of mere citations would help. also presumably the book does not say anything about a _dichotomy_ & that is your own term? no _dichotomy_ seems to be apparent/ clearly defined...  
> **username_3**: For those who stumble over this question: john_leo and me actually worked on this for a while in 2014; find a summary [here](http://reitzig.github.io/research/open-questions/#average-height-of-regular-trees).  

---

## 1 answers

### Answer by username_6 on 2017-10-12. Score: 2

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](http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf) 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.](http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf)) 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.

> **Comments:**
> **username_7**: I think this is a comment and not an answer since it is far from clear wether this attempt works out.  

---

