On the Complexity of Computing Strahler Numbers

The main topic of this paper is the complexity of computing Strahler numbers of binary trees. The Strahler number of a binary tree $t$ is a parameter $\mathrm{𝗌𝗍}(t)$ that can be defined recursively as follows:

• $\mathrm{■}$

  If $t$ consists of a single node then $\mathrm{𝗌𝗍}(t)=0$.

• $\mathrm{■}$

  If the root of $t$ has the left (resp., right) subtree $t_1$ (resp., $t_2$) then

  (1)

The Strahler number is sometimes also called the Horton-Strahler number and first appeared in the area of hydrology, where Horton used it in a paper from 1945 [37] to define the order of a river. The correspondence to binary trees comes from the fact that a system of joining rivers can be viewed as a binary tree (unless there are bifurcations, where a river splits into two streams). In 1952, Strahler [53] (also a hydrologist) further developed Horton’s ideas.

There are numerous applications of Strahler numbers in computer science, where they appeared also under different names (e.g., register function, tree dimension). Ershov [23] showed that the minimal number of registers needed to evaluate an arithmetic expression is exactly the Strahler number of the syntax tree of the arithmetic expression. Another area, where Strahler numbers found many applications, is formal language theory [12, 20, 33, 51]. For context-free grammars, the relation comes from the following fact: Let $G$ be a context-free grammar in Chomsky normal form and let $t$ be a derivation tree of $G$. Then $\mathrm{𝗌𝗍}(t)+1$ is exactly the minimal index among all derivations corresponding to $t$, where the index of a derivation $S=w_0{\Rightarrow }_G{w}_1{\Rightarrow }_G{w}_2{\Rightarrow }_G\mathrm{\cdots }{\Rightarrow }_G{w}_n$ is the maximal number of nonterminals in one of the $w_i$ [33]. Finite-index context-free grammars [3], i.e., grammars where every produced word has a derivation of bounded index, play an important role in the recent decidability proof of the reachability problem in one-dimensional pushdown VASS [7]. Strahler numbers have been also investigated in the context of Newton iteration [24, 46], parity games [16], and social networks [1]. The distribution of the Strahler number of a random tree has been studied by several authors [17, 18, 26, 39, 42]. For more information on Strahler numbers and their applications in computer science, the reader may consult the surveys [25, 56].

The above mentioned applications naturally lead to the question for the precise complexity of computing the Strahler number of a given tree. This problem has a straightforward linear time algorithm: simply compute the Strahler number for all subtrees bottom-up using the definition of the Strahler number. A straightforward recursive algorithm can be implemented on a deterministic Turing machine, running in logspace and polynomial time and equipped with an auxiliary stack, which puts the problem in the class $\mathrm{𝖫𝗈𝗀𝖣𝖢𝖥𝖫}\subseteq {\mathrm{𝖭𝖢}}^2\subseteq \mathrm{𝖣𝖲𝖯𝖠𝖢𝖤}({\log }^{2}n)$ [54]. In particular, Strahler numbers can be computed in polylogarithmic time with polynomially many processors. Alternatively, one can implement a recursive evaluation in $𝒪(\log n\log \log n)$ space. To do so, one uses the fact that the Strahler number of a binary tree with $n$ leaves is bounded by ${\log }_2(n)$, and hence its bit length is $𝒪(\log \log n)$. To the best of our knowledge, the precise complexity of computing Strahler numbers has not been pinpointed yet.

Our first goal is to pinpoint the precise parallel complexity of computing the Strahler number. As explained above, the problem belongs to $\mathrm{𝖭𝖢}$, but the existence of a logspace algorithm for instance is by no means obvious. Formally, we consider the decision problem, asking whether $\mathrm{𝗌𝗍}(t)\ge k$ for a given tree $t$ and a given number $k$. We show that this problem is ${\mathrm{𝖭𝖢}}^1$-complete if $t$ is given in term representation.¹¹1For instance, $bbaabaa$ (or $b(b(a,a),b(a,a))$ with brackets) is the term representation of a complete binary tree of height 2, where $b$ denotes an inner node and $a$ denotes a leaf. Recall that ${\mathrm{𝖭𝖢}}^1$ is the class of all problems that can be solved by a uniform²²2All circuit complexity classes refer to their uniform variants in this paper. In Section 2.2 we will say more about uniformity. family of bounded fan-in circuits of polynomial-size and logarithmic depth, which is a subclass of deterministic logarithmic space ($𝖫$ for short). If the term $t$ is given as a pointer structure, i.e., by an adjacency list or matrix, then checking $\mathrm{𝗌𝗍}(t)\ge k$ is complete for deterministic logspace ($𝖫$ for short).

As a corollary, one can compute in ${\mathrm{𝖭𝖢}}^1$ from a given arithmetic expression $e$ (given in term representation) an optimal straight-line code, i.e., a sequence of statements $x:=y\circ z$ for registers $x,y,z$ and an elementary arithmetic operation $\circ$. Here, optimal means that the number of used registers is minimal. For this, one has to compute the Strahler number of every subexpression of $e$; see also [25, Section 2].

Let us give a high level idea of the ${\mathrm{𝖭𝖢}}^1$-membership proof. The first step is to “balance” the input tree $t$ by computing a so-called tree straight-line program (TSLP) for $t$, whose depth is logarithmic in the size of $t$. This can be done in ${\mathrm{𝖳𝖢}}^0$ by a result from [28]. Roughly speaking, a TSLP is a recursive decomposition of a tree into subtrees and so-called contexts (subtrees, where a smaller subtree is removed). Originally, TSLPs were introduced as a formalism for grammar-based tree compression; see [44] for more details. The next step is to convert the TSLP for $t$ into a bounded fan-in Boolean circuit, that decides whether $\mathrm{𝗌𝗍}(t)\ge k$. Furthermore, the polynomial size and logarithmic depth of the TSLP should be preserved to obtain an ${\mathrm{𝖭𝖢}}^1$ upper bound. A straightforward construction only leads to such a Boolean circuit with unbounded fan-in OR-gates. We obtain a bounded fan-in circuit by carefully analyzing the unary linear term functions computed by contexts when binary nodes are interpreted according to (1).

For the ${\mathrm{𝖭𝖢}}^1$-hardness, we show that the Boolean formula problem, which is one of the best known ${\mathrm{𝖭𝖢}}^1$-complete problems [9], can be reduced to the problem of computing the Strahler number of a tree given in term representation. A similar reduction from the monotone circuit value problem shows that the computation of the Strahler number is $𝖯$-complete when the input tree is given succinctly by a directed acyclic graph (DAG) or a TSLP.

We also consider the problem of checking $\mathrm{𝗌𝗍}(t)\ge k$ for a fixed value $k$ that is not part of the input (the input only consists of the tree $t$). If $t$ is given in term representation (resp., pointer representation) then this problem is ${\mathrm{𝖳𝖢}}^0$-complete for all $k\ge 4$ (resp., $𝖫$-complete for all $k\ge 3$). Moreover, if $t$ is given by a DAG, then this problem belongs to $\mathrm{𝖴𝖫}\cap \mathrm{𝖼𝗈𝖴𝖫}$ for all $k$ ($\mathrm{𝖴𝖫}$ is unambiguous logspace), whereas for TSLP-represented trees the problem is $\mathrm{𝖭𝖫}$-complete for all $k\ge 2$.

In Section 4 we briefly report on some results concerning the maximal Strahler number of derivation trees of a given context-free grammar in Chomsky normal form (CNF). It is known to be undecidable, whether every word produced by a given context-free grammar has a derivation tree of Strahler number at most a given bound $k$ [34, Theorem 5]. Here, we are interested in the question, whether a given CNF-grammar $G$ produces at least one derivation tree $t$ with $\mathrm{𝗌𝗍}(t)\ge k$ for a given number $k$. In the long version [29] we show that this problem is $𝖯$-complete. Finally, we also consider the restriction to acyclic derivation trees. A derivation tree is called acyclic if there is no nonterminal that appears more than once on a path in the derivation tree. The motivation for this restriction comes from the recent paper [45], where it was shown that the intersection non-emptiness problem for a given list of group DFA³³3A group DFA is a deterministic finite automaton, where for every input letter $a$ the $a$-labelled transitions induce a permutation of the set of states. plus a single context-free grammar is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete. For general DFA, this problem is $\mathrm{𝖤𝖷𝖯𝖳𝖨𝖬𝖤}$-complete [55]. Moreover, if the context-free grammar $G$ is such that for some constant $k$, all acyclic derivation trees of $G$ have Strahler number at most $k$, then the intersection problem (with the finite automata restricted to group DFA) is $\mathrm{𝖭𝖯}$-complete. In [45], it was shown that the problem whether a given CNF-grammar has an acyclic derivation tree of Strahler number at least $k$ is in $\mathrm{𝖭𝖯}$, when $k$ is a fixed constant. In the long version [29] we show that the problem is $\mathrm{𝖭𝖯}$-complete already for $k=2$. Finally, when $k$ is part of the input, we show that the problem becomes $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete.

The problem of computing the Strahler number of a given tree is a special instance of a tree evaluation problem: The input is a rooted tree where each leaf is labelled with a value from a domain $A$, and each inner node carries a (suitably specified) function $f:A^r\to A$ where $r$ is the number of its children. The goal is to compute the value of the root, obtained by evaluating the functions at each node from bottom to top. For the case of Strahler numbers we have $A=\mathbb{N}$, every leaf is labelled with $0$ and there is only one binary operation implicitly defined by (1) (or explicitly by (2) on page 2.1). The corresponding algebra will be called the Strahler algebra.

Other prominent examples are the evaluation problems for Boolean formulas such as $(1\vee 0)\wedge 1$ and arithmetic expressions over the natural numbers (or other rings) such as $(1+2)\times (3+4)$. Boolean formula evaluation is ${\mathrm{𝖭𝖢}}^1$-complete [9]. In fact, the acceptance problem of a fixed tree automaton or, equivalently, evaluating an expression over a fixed finite algebra is known to be in ${\mathrm{𝖭𝖢}}^1$ for every finite algebra [28, 43]. By an algebra, we simply mean a set equipped with a set of finitary operations. More surprisingly, arithmetic expressions can be evaluated in deterministic logspace [6, 10, 11] despite the fact that the value of an expression may have polynomially many bits in terms of the size of the expression.

Any algorithm that performs a bottom-up computation over a tree can be seen as an instance of tree evaluation, assuming that the local computation at each node is sufficiently simple. A classical example is Courcelle’s theorem, stating that any monadic second-order (MSO) definable graph property $\mathrm{\Phi }$ can be checked in linear time over graphs of bounded tree-width [15]. The standard proof of Courcelle’s theorem compiles the MSO formula $\mathrm{\Phi }$ into a tree automaton ${𝒜}_{\mathrm{\Phi }}$ that, given a tree decomposition of a graph $G$, verifies whether $\mathrm{\Phi }$ holds in $G$. As remarked above, tree automata can be simulated in ${\mathrm{𝖭𝖢}}^1\subseteq 𝖫$, and therefore Courcelle’s theorem also holds when linear time is replaced by logspace [21] (assuming the logspace version of Bodlaender’s theorem for computing small-width tree decompositions; see [21]). In fact, [21] proves a more powerful solution histogram version of Courcelle’s theorem, which, in the end, reduces to evaluating arithmetic expressions.

Very recently, the tree evaluation problem attracted new attention due to a surprising result by Cook and Mertz [13]. They presented an algorithm that evaluates a complete binary tree of height $h$, whose inner nodes are labelled with binary operations over $\{1,\mathrm{\dots },k\}$ and whose leaves are labelled with elements from $\{1,\mathrm{\dots },k\}$, in space $𝒪(h\log \log k+\log k)$. A straightforward evaluation takes $𝒪(h\log k)$ space. Since the height $h$ is logarithmic in the total input size $n$, the Cook-Mertz algorithm uses $𝒪(\log n\log \log n)$ space, which comes very close to $𝒪(\log n)$ space. It is also a key ingredient in Ryan Williams’ recent proof that any $t$-time bounded Turing machine can be simulated in $𝒪(\sqrt{t\log t})$ space [58]. Notice that the Cook-Mertz algorithm does not give any nontrivial space bounds for the computation of the Strahler number of a tree $t$, since the height of $t$ can be linearly large in its size.

A standard strategy to evaluate a tree $t$ of size $n$ using small space or in parallel polylogarithmic time is to first balance $t$, i.e., to transform it into an equivalent tree of depth $𝒪(\log n)$ and size $\mathrm{𝗉𝗈𝗅𝗒}(n)$. In a second step, the reduced depth can often be exploited to evaluate the tree in parallel or in small space. For example, to evaluate a balanced arithmetic expression in logspace, one can use a result by Ben-Or and Cleve [6] that transforms an arithmetic expression of depth $d$ into a product of $4^d$ many $(3\times 3)$-matrices such that the value of the arithmetic expression appears as a particular entry in the matrix product. The matrix product can in turn be evaluated in logspace using results from [11].

Balancing algorithms were first presented by Spira [52] for Boolean formulas and by Brent [8] for arithmetic expressions. Later work showed that arithmetic expressions can be balanced in ${\mathrm{𝖭𝖢}}^1$ (observed implicitly in [10]) and in fact in ${\mathrm{𝖳𝖢}}^0$ [28]. A generic framework for evaluating trees was presented in [41], which implicitly balances the input tree in ${\mathrm{𝖭𝖢}}^1$. The above mentioned logspace version of Courcelle’s theorem was improved to ${\mathrm{𝖭𝖢}}^1$ [22] (under an appropriate input form) in subsequent work. The first step of that algorithm is to balance a given tree decomposition in ${\mathrm{𝖳𝖢}}^0$.

In general, not every algebra admits such a depth-reduction result, if one requires that the balanced tree is over the same algebra [40, Theorem 1]. The core of most tree balancing approaches is a purely syntactic recursive decomposition of the input tree into subtrees and contexts (subtrees where a subtree was removed) and the depth of this decomposition is bounded logarithmically in the size of the input tree. Formally, this decomposition is a tree straight-line program of logarithmic depth. While subtrees evaluate to elements, contexts describe unary linear term functions over the algebra. For example, over a commutative semiring a context computes an affine function $x\mapsto ax+b$, and can be represented by the parameters $a,b$. Furthermore, the composition of two affine functions can be implemented using semiring operations on these parameters. The main challenge towards efficient tree balancing and tree evaluation over a particular algebra is understanding the structure of its unary linear term functions (called the functional algebra in [41]). In general this can be difficult, as can be seen from the example of a finite algebra: Given a tree automaton with $k$ states, the contexts can induce up to $k^k$ many state transformations. In particular, the space bound of $𝒪(h\log \log k+\log k)$ achieved by the Cook-Mertz algorithm for an algebra of size $k$ cannot be immediately extended to unbalanced trees by applying the Cook-Mertz algorithm to a balanced tree straight-line program for the original tree, since $k$ would blow up to $k^k$. For the special case of the Strahler algebra we provide a characterization of the unary linear term functions computed by contexts in Section 3.

For all $x\in \mathbb{N}$ we have:

We now distinguish the four cases from (4):

We have to show that $[m,i]([\mathrm{\ell },h](x))=[m,i](x)$ for all $x$. Since we obtain from (5):

We have to show $[m,i]([\mathrm{\ell },h](x))=[\mathrm{\ell },i](x)$ for all $x$. With (5) we get

We have to show $[m,i]([\mathrm{\ell },h](x))=[0,i](x)$ for all $x$. Equation (5) yields

We have to show that $[m,i]([\mathrm{\ell },h](x))=[\mathrm{\ell },h](x)$ for all $x$. Equation (5) simplifies for to

This concludes the proof of the lemma. $◀$

Every context $\mathrm{𝗏𝖺𝗅}(A)$ for $A\in N_1$ can be obtained from composing contexts of the form $b(x,t)$ and $b(t,x)$ where $t=\mathrm{𝗏𝖺𝗅}(B)$ for some $B\in N_0$. By Lemma 3.2 it therefore suffices to show that for every $m\in \mathbb{N}$ the mapping $x\mapsto s(x,m)$ (where $s$ is from (2)) is of the form $[\mathrm{\ell },h]$ (then, since $s$ is commutative, the same holds for the mapping $x\mapsto s(m,x)$). It is straightforward to check that $s(x,m)=[m,m](x)$ for all $x\in \mathbb{N}$. $◀$ We are now in the position to prove Theorem 3.1.

We start with the ${\mathrm{𝗎𝖭𝖢}}^1$ upper bound. Let $t\in \mathrm{𝖡𝗂𝗇}$ be a binary tree given in term representation. Let $n$ be the number of leaves of $t$. Hence, we must have $\mathrm{𝗌𝗍}(t)\le {\log }_{2}n$. Our goal is to compute in ${\mathrm{𝗎𝖳𝖢}}^0$ from $t$ and an integer $0\le k\le {\log }_{2}n$ a Boolean circuit ${ℬ}_{t,k}$ of depth $𝒪(\log n)$ such that ${ℬ}_{t,k}$ evaluates to true if and only if $\mathrm{𝗌𝗍}(t)\ge k$. The Boolean circuit ${ℬ}_{t,k}$ is represented in ec-representation, which ensures that it can be unfolded in ${\mathrm{𝗎𝖳𝖢}}^0$ into an equivalent Boolean formula (Lemma 2.2) and then evaluated in ${\mathrm{𝗎𝖭𝖢}}^1$ by Theorem 2.1.

In a first step, we use Theorem 2.4 to compute in ${\mathrm{𝗎𝖳𝖢}}^0$ the ec-representation of a TSLP $𝒢=(N_0,N_1,S,\rho )$ of depth $𝒪(\log n)$ and size $𝒪(n)$ such that $\mathrm{𝗏𝖺𝗅}(𝒢)=t$. Let $N=N_0\cup N_1$. Since the ec-representation of $𝒢$ is available and the depth of $𝒢$ is bounded by $𝒪(\log n)$, one can ensure in ${\mathrm{𝗎𝖳𝖢}}^0$ that all variables in $N$ can be reached from the start variable $S$ (this property is actually satisfied when $𝒢$ is constructed according to [28]). In particular, every variable $A\in N_0$ produces a subtree of $t$ and every variable $A\in N_1$ produces a subcontext of $t$. Hence, every number ${\mathrm{𝗌𝗍}}_A$ is bounded by ${\log }_{2}n$ and we will see in a moment that the same holds for the numbers ${\mathrm{\ell }}_A$ and $h_A$ from Lemma 3.3.

In the following we consider the following set of formal integer variables:

For $X\in \mathrm{\Delta }(𝒢)$ we define the integer $v(X)$ by $v(A_{\mathrm{𝗌𝗍}})={\mathrm{𝗌𝗍}}_A$, $v(A_{\mathrm{\ell }})={\mathrm{\ell }}_A$ and $v(A_h)=h_A$.

We will define a Boolean circuit ${ℬ}_{t,k}$ that contains for all $i\in \mathbb{Z}$ with $|i|\le {\log }_{2}n$ and all $X,Y\in \mathrm{\Delta }(𝒢)$ a gate $[X\le Y+i]$ with the obvious meaning: the gate evaluates to true if and only if $v(X)\le v(Y)+i$. Let $V$ be the set of all such gates $[X\le Y+i]$. It is convenient to allow also gates $[X\le i]$ and $[X\ge i]$. Formally, they can be replaced by $[X\le A_{\mathrm{𝗌𝗍}}+i]$ and $[A_{\mathrm{𝗌𝗍}}\le X-i]$, where $A\in N_0$ is a variable with $\rho (A)=a$ (so that ${\mathrm{𝗌𝗍}}_A=0$). The output gate of ${ℬ}_{t,k}$ is $[S_{\mathrm{𝗌𝗍}}\ge k]$.

The number $i$ is called the offset of the gate $g=[X\le Y+i]$ and we define $N(g)=\{A,B\}$ if $X\in \{A_{\mathrm{𝗌𝗍}},A_{\mathrm{\ell }},A_h\}$ and $Y\in \{B_{\mathrm{𝗌𝗍}},B_{\mathrm{\ell }},B_h\}$. For gates $g_1,g_2\in V$, we write $g_1\succ g_2$ if every variable $B\in N(g_2)$ appears in $\rho (A)$ for some $A\in N(g_1)$. Then the length of every chain $g_1\succ g_2\succ g_3\succ \mathrm{\cdots }\succ g_m$ is bounded by the depth of $𝒢$, which is $𝒪(\log n)$.

To define the wires of ${ℬ}_{t,k}$, first note that the numbers $v(X)$ ($X\in \mathrm{\Delta }(𝒢)$) are computed according to the following rules:

1. (i)

   if $A\in N_0$ and $\rho (A)=a$ then ${\mathrm{𝗌𝗍}}_A=0$,

2. (ii)

   if $A\in N_0$ and $\rho (A)=b(B,C)$ then

3. (iii)

   if $A\in N_0$ and $\rho (A)=B(C)$ then, since ${\mathrm{𝗌𝗍}}_B=[{\mathrm{\ell }}_B,h_B]$,

4. (iv)

   if $A\in N_1$ and $\rho (A)=b(x,B)$ or $\rho (A)=b(B,x)$ then ${\mathrm{\ell }}_A=h_A={\mathrm{𝗌𝗍}}_B$, and

5. (v)

   if $A\in N_1$ and $\rho (A)=B(C(x))$ then by Lemma 3.2 we have:

   (6)