38
$\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.

$\endgroup$
  • 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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.