27
$\begingroup$

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.

Improve this question
$\endgroup$
16
  • $\begingroup$ 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? $\endgroup$
    – Joseph Stack
    Jan 19, 2014 at 13:30
  • $\begingroup$ 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? $\endgroup$
    – john_leo
    Jan 19, 2014 at 13:39
  • $\begingroup$ 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? $\endgroup$
    – f-h
    Jan 19, 2014 at 13:46
  • $\begingroup$ @JosephStack how can the height of a regular tree be infinite? A tree with $n$ nodes cannot have a height greater than $n$. $\endgroup$
    – john_leo
    Jan 19, 2014 at 13:50
  • 1
    $\begingroup$ @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 :) $\endgroup$
    – Joseph Stack
    Jan 19, 2014 at 15:10

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I think this is a comment and not an answer since it is far from clear wether this attempt works out. $\endgroup$
    – Danny
    Oct 18, 2017 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.