<p>Let <span class="math-container">$\Sigma$</span> be a ranked alphabet, and let <span class="math-container">$T(\Sigma)$</span> be the set of all finite <span class="math-container">$\Sigma$</span>-labeled trees. A regular tree language <span class="math-container">$L \subseteq T(\Sigma)$</span> is recognized by a finite tree automaton <span class="math-container">$A = (Q, \Sigma, \delta, F)$</span>. We measure the size of a tree <span class="math-container">$t$</span> by its number of nodes, denoted <span class="math-container">$|t|$</span>, and let <span class="math-container">$C(n)$</span> be the number of trees in <span class="math-container">$L$</span> of size <span class="math-container">$n$</span>. We wish to characterize when <span class="math-container">$C(n) = n^{O(1)}$</span> using only tree-structural properties.</p>
<p>To capture boundedness, augment <span class="math-container">$\Sigma$</span> by adding placeholder symbols <span class="math-container">$\{\diamond_1, \dots, \diamond_m\}$</span> of specified arities, forming <span class="math-container">$\Sigma_\diamond = \Sigma \cup \{\diamond_1,\dots,\diamond_m\}$</span>. Choose a finite set <span class="math-container">$\mathcal{T} = \{T_1,\dots,T_k\} \subseteq T(\Sigma_\diamond)$</span> of template trees. Each template <span class="math-container">$T_i$</span> is a finite <span class="math-container">$\Sigma_\diamond$</span>-tree that may contain placeholders. Define a composition function</p>
<p><span class="math-container">$$\phi : (\mathcal{T} \cup T(\Sigma))^p \longrightarrow T(\Sigma),$$</span></p>
<p>which replaces each placeholder <span class="math-container">$\diamond_j$</span> in a template by an input tree of matching arity, preserving the overall tree structure. For any sequence of input trees <span class="math-container">$(S_1,\dots,S_p)$</span>, the result <span class="math-container">$\phi(S_1,\dots,S_p)$</span> is an ordinary <span class="math-container">$\Sigma$</span>-tree. This operation is well-defined in the sense that each <span class="math-container">$\diamond_j$</span> has a fixed number of children, and only subtrees of the correct rank can be substituted.</p>
<p>A tree <span class="math-container">$t \in T(\Sigma)$</span> admits a <span class="math-container">$(\mathcal{T},\phi)$</span>-decomposition of depth <span class="math-container">$p$</span> if there is a sequence <span class="math-container">$(S_1,\dots,S_p)$</span> with each <span class="math-container">$S_\ell \in \mathcal{T}\cup T(\Sigma)$</span> such that</p>
<p><span class="math-container">$$t = \phi(S_1,\dots,S_p).$$</span></p>
<p>The depth <span class="math-container">$p$</span> corresponds to how many times we apply the composition function <span class="math-container">$\phi$</span>. Say that <span class="math-container">$L$</span> is template bounded with depth <span class="math-container">$O(\log n)$</span> if every tree <span class="math-container">$t\in L$</span> of size <span class="math-container">$n$</span> admits such a decomposition of depth at most <span class="math-container">$c \log(n)$</span> for some constant <span class="math-container">$c$</span>. This template-boundedness is the direct tree analog of &quot;boundedness&quot; in word languages and results in the following equivalence:</p>
<ol>
<li><p>If <span class="math-container">$L$</span> is template bounded, then <span class="math-container">$C(n) \leq n^{O(1)}$</span>. Since there are only finitely many templates in <span class="math-container">$\mathcal{T}$</span> and each decomposition for a size-<span class="math-container">$n$</span> tree has depth at most <span class="math-container">$c\log(n)$</span>, the number of ways to pick templates at each step is at most <span class="math-container">$k^{O(\log n)}$</span>, which is <span class="math-container">$n^{O(1)}$</span>. Once the sequence <span class="math-container">$(S_1,\dots,S_p)$</span> is fixed, the result of <span class="math-container">$\phi$</span> is unique, preventing exponential blow-up.</p>
</li>
<li><p>Conversely, if <span class="math-container">$C(n) \leq n^{O(1)}$</span>, we can encode <span class="math-container">$L$</span> size-preservingly into a context-free word language <span class="math-container">$L' \subseteq \Sigma'^*$</span>. Polynomial growth of <span class="math-container">$L$</span> implies polynomial growth of <span class="math-container">$L'$</span>, which implies <span class="math-container">$L'$</span> is a bounded context-free language in the classic sense <span class="math-container">$\subseteq w_1^* \cdots w_\ell^*$</span>. Translating that bounded structure back to the tree world produces a finite set of tree templates together with a composition operation that reconstructs each tree of <span class="math-container">$L$</span> in at most logarithmic depth. The placeholders <span class="math-container">$\diamond_j$</span> in each template correspond to subtrees recognized by certain states of the underlying finite tree automaton, ensuring that no step in the decomposition can branch in an unbounded manner.</p>
</li>
</ol>

CC BY-SA 4.0
2024-12-22T05:04:14.757Z
2024-12-22T05:04:14.757Z
Alex Rudimer
<p>Let <span class="math-container">$L$</span> be a regular tree language and <span class="math-container">$C(n)$</span> be the number of trees in <span class="math-container">$L$</span> of size <span class="math-container">$n\in\mathbb{N}$</span>. Is there a &quot;structural&quot; condition on <span class="math-container">$L$</span> that is equivalent to <span class="math-container">$C(n) = n^{O(1)}$</span>?</p>
<p>There are reasons to believe that there should be. If <span class="math-container">$L'$</span> is a context-free word language and <span class="math-container">$C'(n)$</span> counts its words of size <span class="math-container">$n$</span>, then <span class="math-container">$C'(n) = n^{O(1)}$</span> if and only if <span class="math-container">$L'$</span> is a &quot;bounded language&quot;, which means that there exist words <span class="math-container">$w_1,\dots,w_k$</span> such that <span class="math-container">$L' \subseteq (w_1)^* \dots (w_k)^*$</span>. (According to the introduction of <a href="https://doi.org/10.1142/S0129054110007441" rel="nofollow noreferrer">https://doi.org/10.1142/S0129054110007441</a> &quot;this result has been independently discovered at least six times&quot;.) Moreover, regular tree languages can be encoded as context-free word languages in a size-preserving way (e.g. using reverse Polish notation). So <span class="math-container">$C(n) = n^{O(1)}$</span> if and only if the language of encodings of trees in <span class="math-container">$L$</span> is bounded.</p>
<p>But I wonder whether some necessary and sufficient condition can be stated directly on the shape of the trees themselves. Does something like this exist in the literature?</p>

<automata-theory>
Characterizing regular tree languages of polynomial growth
Lê Thành Dũng 'Tito' Nguyễn
# Characterizing regular tree languages of polynomial growth

(Asked by: username_0 on 2024-12-21)

Let $L$ be a regular tree language and $C(n)$ be the number of trees in $L$ of size $n\in\mathbb{N}$. Is there a "structural" condition on $L$ that is equivalent to $C(n) = n^{O(1)}$?

There are reasons to believe that there should be. If $L'$ is a context-free word language and $C'(n)$ counts its words of size $n$, then $C'(n) = n^{O(1)}$ if and only if $L'$ is a "bounded language", which means that there exist words $w\_1,\dots,w\_k$ such that $L' \subseteq (w\_1)^\* \dots (w\_k)^\*$. (According to the introduction of <https://doi.org/10.1142/S0129054110007441> "this result has been independently discovered at least six times".) Moreover, regular tree languages can be encoded as context-free word languages in a size-preserving way (e.g. using reverse Polish notation). So $C(n) = n^{O(1)}$ if and only if the language of encodings of trees in $L$ is bounded.

But I wonder whether some necessary and sufficient condition can be stated directly on the shape of the trees themselves. Does something like this exist in the literature?

**Tags:** automata-theory

---

## 1 answers

### Answer by username_1 on 2024-12-22. Score: -2

Let $\Sigma$ be a ranked alphabet, and let $T(\Sigma)$ be the set of all finite $\Sigma$-labeled trees. A regular tree language $L \subseteq T(\Sigma)$ is recognized by a finite tree automaton $A = (Q, \Sigma, \delta, F)$. We measure the size of a tree $t$ by its number of nodes, denoted $|t|$, and let $C(n)$ be the number of trees in $L$ of size $n$. We wish to characterize when $C(n) = n^{O(1)}$ using only tree-structural properties.

To capture boundedness, augment $\Sigma$ by adding placeholder symbols $\{\diamond\_1, \dots, \diamond\_m\}$ of specified arities, forming $\Sigma\_\diamond = \Sigma \cup \{\diamond\_1,\dots,\diamond\_m\}$. Choose a finite set $\mathcal{T} = \{T\_1,\dots,T\_k\} \subseteq T(\Sigma\_\diamond)$ of template trees. Each template $T\_i$ is a finite $\Sigma\_\diamond$-tree that may contain placeholders. Define a composition function

$$\phi : (\mathcal{T} \cup T(\Sigma))^p \longrightarrow T(\Sigma),$$

which replaces each placeholder $\diamond\_j$ in a template by an input tree of matching arity, preserving the overall tree structure. For any sequence of input trees $(S\_1,\dots,S\_p)$, the result $\phi(S\_1,\dots,S\_p)$ is an ordinary $\Sigma$-tree. This operation is well-defined in the sense that each $\diamond\_j$ has a fixed number of children, and only subtrees of the correct rank can be substituted.

A tree $t \in T(\Sigma)$ admits a $(\mathcal{T},\phi)$-decomposition of depth $p$ if there is a sequence $(S\_1,\dots,S\_p)$ with each $S\_\ell \in \mathcal{T}\cup T(\Sigma)$ such that

$$t = \phi(S\_1,\dots,S\_p).$$

The depth $p$ corresponds to how many times we apply the composition function $\phi$. Say that $L$ is template bounded with depth $O(\log n)$ if every tree $t\in L$ of size $n$ admits such a decomposition of depth at most $c \log(n)$ for some constant $c$. This template-boundedness is the direct tree analog of "boundedness" in word languages and results in the following equivalence:

1. If $L$ is template bounded, then $C(n) \leq n^{O(1)}$. Since there are only finitely many templates in $\mathcal{T}$ and each decomposition for a size-$n$ tree has depth at most $c\log(n)$, the number of ways to pick templates at each step is at most $k^{O(\log n)}$, which is $n^{O(1)}$. Once the sequence $(S\_1,\dots,S\_p)$ is fixed, the result of $\phi$ is unique, preventing exponential blow-up.
2. Conversely, if $C(n) \leq n^{O(1)}$, we can encode $L$ size-preservingly into a context-free word language $L' \subseteq \Sigma'^\*$. Polynomial growth of $L$ implies polynomial growth of $L'$, which implies $L'$ is a bounded context-free language in the classic sense $\subseteq w\_1^\* \cdots w\_\ell^\*$. Translating that bounded structure back to the tree world produces a finite set of tree templates together with a composition operation that reconstructs each tree of $L$ in at most logarithmic depth. The placeholders $\diamond\_j$ in each template correspond to subtrees recognized by certain states of the underlying finite tree automaton, ensuring that no step in the decomposition can branch in an unbounded manner.


---

