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

Improve this question
$\endgroup$
5
  • 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, 2013 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, 2013 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, 2014 at 14:45
  • 1
    $\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, 2018 at 14:10
  • $\begingroup$ I’m voting to close this question because it was cross-posted. I suggest posting any answers over on TCS.SE. $\endgroup$
    – D.W. ♦
    Dec 23, 2022 at 23:57

0

Reset to default