Dynamic Membership for Regular Tree Languages

We give preliminaries in Section 2 and introduce the dynamic membership problem. We then give in Section 3 some further preliminaries about forest algebras, which are instrumental to the proof of our results. We then present our first contribution in Section 4, namely, an $O(\log n/\log \log n)$ algorithm for dynamic membership to any fixed regular tree language. We then introduce almost-commutative languages in Section 5 and show that dynamic membership to these languages is in $O(1)$. In Section 6 we show our matching lower bound: in the presence of a neutral letter, and assuming that prefix-$U_1$ cannot be solved in constant time, then the dynamic membership problem cannot be solved in constant time for any non-almost-commutative regular language. We conclude in Section 7.

Because of space limitations, detailed proofs are deferred to the full version [2]. Note that a version of the results of Sections 5 and 6 was presented in [7] but never formally published.

We consider ordered forests of rooted, unranked, ordered trees on a finite alphabet $\mathrm{\Sigma }$, and simply call them forests. Formally, we define $\mathrm{\Sigma }$-forests and $\mathrm{\Sigma }$-trees by mutual induction: a $\mathrm{\Sigma }$-forest is a (possibly empty) ordered sequence of $\mathrm{\Sigma }$-trees, and a $\mathrm{\Sigma }$-tree consists of a root node with a label in $\mathrm{\Sigma }$ and with a $\mathrm{\Sigma }$-forest of child nodes.

We assume familiarity with standard terminology on trees including parent node, children node, ancestors, descendants, root nodes, siblings, sibling sets, previous sibling, next sibling, prefix order, etc.; see [11] for details. As we work with ordered forests, we will always consider root nodes to be siblings, and define the previous sibling and next sibling relationships to also apply to roots. We will often abuse notation and identify forests with their sets of nodes, e.g., for a forest $F$, we define functions on $F$ to mean functions defined on the nodes of $F$. We say that two forests have the same shape if they are identical up to changing the labels of their nodes (which are elements of $\mathrm{\Sigma }$). The size $|F|$ of a $\mathrm{\Sigma }$-forest $F$ is its number of nodes, and we write ${|F|}_a$ for $a\in \mathrm{\Sigma }$ to denote the number of occurrences of $a$ in $F$.

A forest language $L$ over an alphabet $\mathrm{\Sigma }$ is a subset of $\mathrm{\Sigma }$-forests, and a tree language is a subset of $\mathrm{\Sigma }$-trees: throughout the paper we study forest languages, but of course our results extend to tree languages as well. We write $\overline{L}$ for the complement of $L$. We will be specifically interested in regular forest languages: among many other equivalent characterizations [11], these can be formalized via finite automata, which we formally introduce below (first for words and then for forests).

A deterministic word automaton over a set $S$ is a tuple $A=(Q,F,q_0,\delta )$ where $Q$ is a finite set of states, $F\subseteq Q$ is a subset of final states, $q_0\in Q$ is the initial state, and $\delta :Q\times S\to Q$ is a transition function. For $w=s_1\mathrm{\cdots }{s}_k$ a word over $S$, the state reached by $A$ when reading $w$ is defined inductively as usual: if $w=ϵ$ is the empty word then the state reached is $q_0$, otherwise the state reached is $\delta (q,s_k)$ with $q$ the state reached when reading $s_1\mathrm{\cdots }{s}_{k-1}$. The word $w$ is accepted if the state reached by $A$ when reading $w$ is in $F$.

We define forest automata over forests, which recognize forest languages by running a word automaton over the sibling sets. These automata are analogous to the hedge automata of [11] (where horizontal transitions are specified by regular languages), and to the forest automata of [10] (where horizontal transitions are specified by a monoid). Formally, a forest automaton over $\mathrm{\Sigma }$ is a tuple $A=(Q,A^{\prime },\delta )$ where $Q$ is a finite set of states, $A^{\prime }=(Q^{\prime },F^{\prime },q_0^{\prime },{\delta }^{\prime })$ is a word automaton over the set $Q$, and $\delta :Q^{\prime }\times \mathrm{\Sigma }\to Q$ is a vertical transition function which associates to every state $q^{\prime }\in Q^{\prime }$ of $A^{\prime }$ and letter $a\in \mathrm{\Sigma }$ a state $\delta (q^{\prime },a)\in Q$. The run of $A=(Q,A^{\prime },\delta )$ on a $\mathrm{\Sigma }$-tree $T$ is a function $\rho$ from $T$ to $Q$ defined inductively as follows:

• $\mathrm{■}$

  For $u$ a leaf of $T$ with label $a\in \mathrm{\Sigma }$, we have $\rho (u)=\delta (q_0^{\prime },a)$ for $q_0^{\prime }$ the initial state of $A^{\prime }$;

• $\mathrm{■}$

  For $u$ an internal node of $T$ with label $a\in \mathrm{\Sigma }$, letting $u_1,\mathrm{\dots },u_k$ be its successive children, and letting $q_i≔\rho (u_i)$ for all $1\le i\le k$ be the inductively computed images of the run, for $q$ the state reached in $A^{\prime }$ when reading the word $q_1\mathrm{\cdots }{q}_k$, we let $\rho (u)≔\delta (q,a)$.

We say that a $\mathrm{\Sigma }$-forest $F$ is accepted by the forest automaton $A$ if, letting $T_1,\mathrm{\dots },T_k$ be the trees of $F$ in order, and letting $q_1,\mathrm{\dots },q_k$ be the states to which the respective roots of the $T_1,\mathrm{\dots },T_k$ are mapped by the respective runs of $A$, then the word $q_1\mathrm{\cdots }{q}_k$ is accepted by the word automaton $A^{\prime }$. (In particular, the empty forest is accepted iff $q_0^{\prime }\in F^{\prime }$.) The language of $A$ is the set of $\mathrm{\Sigma }$-forests that it accepts.

We consider relabeling updates on forests $F$, that change node labels without changing the tree shape. A relabeling update gives a node $u$ of $F$ (e.g., as a pointer to that node) and a label $a\in \mathrm{\Sigma }$, and changes the label of the node $u$ to $a$.

We fix a regular language $L$ of $\mathrm{\Sigma }$-forests given by a fixed forest automaton $A$, and we are given as input a $\mathrm{\Sigma }$-forest $F$. We can compute in linear time whether $A$ accepts $F$. The dynamic membership problem for $L$ is the task of maintaining whether the current forest belongs to $L$, under relabeling updates. We study the complexity of this problem, defined as the worst-case running time of an algorithm after each update, expressed as a function of the size $|F|$ of $F$. Note that the language $L$ is assumed to be fixed, and is not accounted for in the complexity. We work in the RAM model with unit cost and logarithmic word size, and consider dynamic membership algorithms that run a linear-time preprocessing on the input forest $F$ to build data structures used when processing updates. (By contrast, our lower bound results will hold without the assumption that the preprocessing is in linear time.)

As we reviewed in the introduction, for any fixed regular forest language, it is folklore that the dynamic membership problem on a tree with $n$ nodes can be solved under relabeling updates in time $O(\log n)$ per update: see for instance [3]. Further, for some forest languages, some unconditional lower bounds in $\mathrm{\Omega }(\log n/\log \log n)$ are known. This includes some forest languages defined from intractable word languages, for instance the forest language $L_1$ on alphabet $\mathrm{\Sigma }=\{0,1,\mathrm{\#}\}$ where the word on ${\mathrm{\Sigma }}^{\ast }$ formed by the leaves in prefix order is required to fall in the word language $L_2≔{(0^{\ast }{10}^{\ast }{10}^{\ast })}^{\ast }\mathrm{\#}{\mathrm{\Sigma }}^{\ast }$, i.e., a unique $\mathrm{\#}$ with an even number of $1$’s before it. Indeed, dynamic membership to $L_2$ (under letter substitutions) admits an $\mathrm{\Omega }(\log n/\log \log n)$ lower bound from the prefix-${\mathbb{Z}}_2$ problem (see [13, Theorem 3], and [12, 4]), hence so does $L_1$. Intractable forest languages also include languages corresponding to the existential marked ancestor problem [1], e.g., the language $L_3$ on alphabet $\mathrm{\Sigma }=\{e,m,\mathrm{\#}\}$ where we have a unique node $u$ labeled $\mathrm{\#}$ and we require that $u$ has an ancestor labeled $m$. Indeed, the existential marked ancestor problem of [1] allows us to mark and unmark nodes over a fixed tree (corresponding to letters $e$ for unmarked nodes and $m$ for marked nodes), and allows us to query whether a node (labeled $\mathrm{\#}$) has a marked ancestor. Thus, the existential marked ancestor problem immediately reduces to dynamic membership for $L_3$, which inherits the $\mathrm{\Omega }(\log n/\log \log n)$ lower bound from [1].

A monoid $M$ is a set equipped with an associative composition law featuring a neutral element, that is, an element $e$ such that $ex=xe=x$ for all $x$ in $M$. We write the composition law of monoids multiplicatively, i.e., we write $xy$ for the composition of $x$ and $y$. The idempotent power of an element $v$ in a finite monoid $M$, written $v^{\omega }$, is $v$ raised to the least integer $\omega$ such that $v^{\omega }=v^{\omega }{v}^{\omega }$: see [21, Chp. II, Prop. 6.31] for a proof that every element has an idempotent power. The idempotent power of $M$ is a value $m\in \mathbb{N}$ ensuring that, for each $v\in M$, we have $v^m{v}^m=v^m$: this can be achieved by taking any common multiple of the exponents $\omega$ for the idempotent powers of all elements of $M$.

A forest algebra [10] is a pair $(V,H)$ of two monoids. The monoid $V$ is the vertical monoid, with vertical composition written ${\odot }_{\mathrm{VV}}$ and neutral element written $\mathrm{\square }$. The monoid $H$ is the horizontal monoid, with horizontal concatenation denoted ${\oplus }_{\mathrm{HH}}$, and with neutral element written $ϵ$. Further, we have three composition laws: ${\odot }_{\mathrm{VH}}:V\times H\to H$, ${\oplus }_{\mathrm{VH}}:V\times H\to V$, and ${\oplus }_{\mathrm{HV}}:H\times V\to V$. We require that the following relations hold:

• $\mathrm{■}$

  Action (composition): for every $v,w\in V$ and $h\in H$, $(v{\odot }_{\mathrm{VV}}w){\odot }_{\mathrm{VH}}h=v{\odot }_{\mathrm{VH}}(w{\odot }_{\mathrm{VH}}h)$.

• $\mathrm{■}$

  Action (neutral): for every $h\in H$, $\mathrm{\square }{\odot }_{\mathrm{VH}}h=h$.

• $\mathrm{■}$

  Mixing: for every $v\in V$ and $h,g\in H$, we have $(v{\oplus }_{\mathrm{VH}}h){\odot }_{\mathrm{VH}}g=(v{\odot }_{\mathrm{VH}}g){\oplus }_{\mathrm{HH}}h$ and $(h{\oplus }_{\mathrm{HV}}v){\odot }_{\mathrm{VH}}g=h{\oplus }_{\mathrm{HH}}(v{\odot }_{\mathrm{VH}}g)$.

• $\mathrm{■}$

  Faithfulness: for every distinct $v,w\in V$, there exists $h\in H$ such that $v{\odot }_{\mathrm{VH}}h\ne w{\odot }_{\mathrm{VH}}h$.

We explain in the appendix of the full version [2] how this formalism slightly differs from that of [10] but is in fact equivalent. We often abuse notation and write $\oplus$ to mean one of ${\oplus }_{\mathrm{HH}},{\oplus }_{\mathrm{HV}},{\oplus }_{\mathrm{VH}}$ and write $\odot$ to mean one of ${\odot }_{\mathrm{VH}},{\odot }_{\mathrm{VV}}$.

We almost always assume that forest algebras are finite, i.e., the horizontal and vertical monoids $H$ and $V$ are both finite. The only exception is the free forest algebra ${\mathrm{\Sigma }}^{\nabla }=({\mathrm{\Sigma }}^{\mathrm{V}},{\mathrm{\Sigma }}^{\mathrm{H}})$. Here, ${\mathrm{\Sigma }}^{\mathrm{H}}$ is the set of all $\mathrm{\Sigma }$-forests, and ${\mathrm{\Sigma }}^{\mathrm{V}}$ is the set of all $\mathrm{\Sigma }$-contexts, i.e., $\mathrm{\Sigma }$-forests having precisely one node that carries the special label $\mathrm{\square }\notin \mathrm{\Sigma }$: further, this node must be a leaf. The $\oplus$-laws denote horizontal concatenation: of two forests for ${\oplus }_{\mathrm{HH}}$, and of a forest and a context for ${\oplus }_{\mathrm{HV}}$ and ${\oplus }_{\mathrm{VH}}$. (Note that two contexts cannot be horizontally concatenated because the result would have two nodes labeled $\mathrm{\square }$.) We write the $\oplus$-laws as $+$, and remark that they are not commutative. The $\odot$-laws are the context application operations of plugging the forest (for ${\odot }_{\mathrm{VH}}$) or context (for ${\odot }_{\mathrm{VV}}$) on the right in place of the $\mathrm{\square }$-node of the context on the left. We write the $\odot$-laws functionally, i.e., for $s\in {\mathrm{\Sigma }}^{\mathrm{V}}$ and for $u\in {\mathrm{\Sigma }}^{\mathrm{V}}$ or $f\in {\mathrm{\Sigma }}^{\mathrm{H}}$ we write $s(u)$ to mean $s{\odot }_{\mathrm{VV}}u$ and write $s(f)$ to mean $s{\odot }_{\mathrm{VH}}f$.

We write $\mathrm{\square }\in {\mathrm{\Sigma }}^{\mathrm{V}}$ for the trivial $\mathrm{\Sigma }$-context consisting only of a single node labeled $\mathrm{\square }$, we write $ϵ\in {\mathrm{\Sigma }}^{\mathrm{H}}$ for the empty forest, and for $a\in \mathrm{\Sigma }$ we write $a_{\mathrm{\square }}\in {\mathrm{\Sigma }}^{\mathrm{V}}$ the $\mathrm{\Sigma }$-context which consists of a single root node labeled $a$ with a single child labeled $\mathrm{\square }$. Note that ${\mathrm{\Sigma }}^{\mathrm{V}}$ and ${\mathrm{\Sigma }}^{\mathrm{H}}$ are spanned by $ϵ$ and $\mathrm{\square }$ and by the $a_{\mathrm{\square }}$ via context application and concatenation.

A morphism of forest algebras [10] consists of two functions that map forests to forests and contexts to contexts and are compatible with the internal operations. Formally, a morphism from $(V,H)$ to $(V^{\prime },H^{\prime })$ is a pair of functions ${\mu }_{\mathrm{V}}:V\to V^{\prime },{\mu }_{\mathrm{H}}:H\to H^{\prime }$ where:

• $\mathrm{■}$

  ${\mu }_{\mathrm{V}}$ is a monoid morphism: for all $v,w\in V$, we have ${\mu }_{\mathrm{V}}(v\cdot w)={\mu }_{\mathrm{V}}(v)\cdot {\mu }_{\mathrm{V}}(w)$ and ${\mu }_{\mathrm{V}}(\mathrm{\square })=\mathrm{\square }$ where $\cdot$ and $\mathrm{\square }$ are interpreted in the corresponding monoid.

• $\mathrm{■}$

  ${\mu }_{\mathrm{H}}$ is a monoid morphism: for all $h,g\in H$, we have ${\mu }_{\mathrm{H}}(h+g)={\mu }_{\mathrm{H}}(h)+{\mu }_{\mathrm{H}}(g)$ and ${\mu }_{\mathrm{H}}(ϵ)=ϵ$ where $+$ and $ϵ$ are interpreted in the corresponding monoid.

• $\mathrm{■}$

  for every $v\in V$, $h\in H$, we have ${\mu }_{\mathrm{H}}(v{\odot }_{\mathrm{VH}}h)={\mu }_{\mathrm{V}}(v){\odot }_{\mathrm{VH}}{\mu }_{\mathrm{H}}(h)$.

• $\mathrm{■}$

  for every $v\in V$, $h\in H$, we have ${\mu }_{\mathrm{V}}(v{\oplus }_{\mathrm{VH}}h)={\mu }_{\mathrm{V}}(v){\oplus }_{\mathrm{VH}}{\mu }_{\mathrm{H}}(h)$ and ${\mu }_{\mathrm{V}}(h{\oplus }_{\mathrm{HV}}v)={\mu }_{\mathrm{H}}(h){\oplus }_{\mathrm{HV}}{\mu }_{\mathrm{V}}(v)$.

We often abuse notation and write a morphism $\mu$ to mean the function that applies ${\mu }_{\mathrm{V}}$ to $\mathrm{\Sigma }$-contexts and ${\mu }_{\mathrm{H}}$ to $\mathrm{\Sigma }$-forests. For any alphabet $\mathrm{\Sigma }$ and forest algebra $(V,H)$, given a function $g$ from the alphabet $\mathrm{\Sigma }$ to $V$, we extend it to a morphism ${\mu }_{\mathrm{V}},{\mu }_{\mathrm{H}}$ from the free forest algebra to $(V,H)$ in the only way compatible with the requirements above, i.e.:

• $\mathrm{■}$

  For a sequence of $\mathrm{\Sigma }$-trees $F=t_1,\mathrm{\dots },t_k$ where at most one $t_i$ is a $\mathrm{\Sigma }$-context, letting $x_i≔\mu (t_i)$ for each $i$ be inductively defined, then $\mu (F)≔x_1\oplus \mathrm{\cdots }\oplus x_k$.

• $\mathrm{■}$

  For a $\mathrm{\Sigma }$-tree or $\mathrm{\Sigma }$-context $t$ with root node $u$ labeled $a\in \mathrm{\Sigma }$, letting $F$ be the (possibly empty) sequence of children of $u$ (of which at most one is a context, and for which $\mu (F)$ was inductively defined), then we set $\mu (t)≔(g(a))\odot \mu (F)$.

A forest language $L$ over $\mathrm{\Sigma }$ is recognized by a forest algebra $(V,H)$ if there is a subset $H^{\prime }\subseteq H$ and a function from $\mathrm{\Sigma }$ to $V$ defining a morphism ${\mu }_{\mathrm{V}},{\mu }_{\mathrm{H}}$ having the following property: a $\mathrm{\Sigma }$-forest $F$ is in $L$ iff ${\mu }_{\mathrm{H}}(F)\in H^{\prime }$.

Regular forest languages can be related to forest algebras via the notion of syntactic forest algebra. Indeed, a forest language is regular iff it is recognized by some forest algebra (see [10, Proposition 3.19]). Specifically, we will consider the syntactic forest algebra of a regular forest language $L$: this forest algebra recognizes $L$, it is minimal in a certain sense, and it is unique up to isomorphism. We omit the formal definition of the syntactic forest algebra $(V,H)$ of $L$ (see [10, Definition 3.13] for details). We will just use the fact that it recognizes $L$ for a certain function $g$ from $\mathrm{\Sigma }$ to $V$ and associated morphism ${\mu }_{\mathrm{V}},{\mu }_{\mathrm{H}}$ from $\mathrm{\Sigma }$-forests to $(V,H)$, called the syntactic morphism, and satisfying the following:

• $\mathrm{■}$

  Surjectivity: for any element $v$ of $V$, there is a $\mathrm{\Sigma }$-context $c$ such that ${\mu }_{\mathrm{V}}(c)=v$;

• $\mathrm{■}$

  Minimality: for any two $\mathrm{\Sigma }$-contexts $c$ and $c^{\prime }$, if ${\mu }_{\mathrm{V}}(c)\ne {\mu }_{\mathrm{V}}(c^{\prime })$, then there is a $\mathrm{\Sigma }$-context $r$ and a $\mathrm{\Sigma }$-forest $s$ such that exactly one of $r(c(s))$ and $r(c^{\prime }(s))$ belongs to $L$.

We will study the analogue of the dynamic membership problem for forest algebras, which is that of computing the evaluation of an expression. More precisely, for $(V,H)$ a forest algebra, a $(V,H)$-forest is a forest where each internal node is labeled by an element of $V$ and where each leaf is labeled with an element of $H$ – but there may be one leaf, called the distinguished leaf, which is labeled with an element of $V$. The evaluation of a $(V,H)$-forest $F$ is the image of $F$ by the morphism obtained by extending the function $g$ which maps elements of $V$ to themselves and maps elements $f$ of $H$ to the context $c_f≔f{\oplus }_{\mathrm{HV}}\mathrm{\square }$ (so that $c_f{\odot }_{\mathrm{VH}}ϵ=f$). Remark that the forest $F$ evaluates to an element of $V$ if it has a distinguished leaf, and to $H$ otherwise.

The (non-restricted) dynamic evaluation problem for $(V,H)$ then asks us to maintain the evaluation of the $(V,H)$-forest $F$ under relabeling updates which can change the label of internal nodes of $F$ (in $V$) and of leaf nodes of $F$ (in $H$ or in $V$, but ensuring that there is always at most one distinguished leaf in $F$). Again, we assume that the forest algebra $(V,H)$ is constant, and we measure the complexity as a function of the size $|F|$ of the input forest (note that updates never change $|F|$ or the shape of $F$). The restricted dynamic evaluation problem for $(V,H)$ adds the restriction that the label of leaves always stays in $H$ (initially and after all updates), so that $F$ always evaluates to an element of $H$.

We will use the dynamic evaluation problem in the next section for our $O(\log n/\log \log n)$ upper bound. Indeed, it generalizes the dynamic membership problem in the following sense:

A clustering of a forest will be defined by partitioning its vertices into connected sets, where connectedness is defined using the sibling and first-child edges.

Note that the edges used in LCRS-adjacency are not the edges of $F$, but those of a left-child-right-sibling representation of $F$ (hence the name). For instance, the set $\{u,u^{\prime }\}\subseteq F$ formed of a node $u$ and its parent $u^{\prime }$ is not connected unless $u$ is the first child of $u^{\prime }$. To define clusters and clusterings, we will use LCRS-adjacency, together with a notion of border nodes that correspond to the “holes” of clusters:

When we have defined a $k$-clustering, it induces a forest of clusters in the following way:

Remark that the trivial equivalence relation (putting each node in its own cluster) is vacuously a $k$-clustering in which the border nodes are precisely the internal nodes: we call this the trivial $k$-clustering, and its forest of clusters is isomorphic to $F$.

To solve the dynamic evaluation problem on $F$ using a clustering $\equiv$, we will now explain how the evaluation of the $(V,H)$-forest $F$ can reduce to the evaluation of the forest of clusters $F^{\equiv }$ with a suitable labeling. To define this labeling, let us first define the evaluation of a cluster in $F$:

We now see $F^{\equiv }$ as a $(V,H)$-forest, with each cluster labeled by its evaluation in $F$: Then:

This property is what we use in the recursive scheme: to solve the dynamic evaluation problem on the input $(V,H)$-forest $F$, during the preprocessing we will compute a clustering $\equiv$ of $F$ and compute the evaluation of clusters and of the forest of clusters $F^{\equiv }$. Given a relabeling update on $F$, we will apply it to its cluster $C$ and recompute the evaluation of $C$; this gives us a relabeling update to apply to the node $C$ on the forest of clusters $F^{\equiv }$, and we can recursively apply the scheme to $F^{\equiv }$ to maintain the evaluation of $F^{\equiv }$. What remains is to explain how we can efficiently compute a clustering of a forest $F$ that ensures that the forest of clusters $F^{\equiv }$ is “small enough”.

Here is what we want to establish:

Our algorithm starts with the trivial $k$-clustering and iteratively merges clusters. Formally, merging two clusters $C$ and $C^{\prime }$ means setting them to be equivalent under $\equiv$, and we call $C$ and $C^{\prime }$ mergeable when doing so leads to a $k$-clustering. Of course, we will only merge mergeable clusters in the algorithm.

We say that the $k$-clustering is saturated if it does not contain two mergeable clusters. Our definition of clusters is designed to ensure that, as soon as the clustering is saturated, there are enough large clusters so that the number of clusters (i.e., the size of the forest of clusters) satisfies the bound of Proposition 4.7, no matter how clusters were merged. Namely:

We focus on clusters with zero or one child in the forest of clusters. We consider potential merges of these clusters with their only child, with their preceding sibling, or with their parent (if they are the first child). This allows us to show that, provided that there are multiple clusters, a constant fraction of them have to contain at least $k/2$ nodes, so the number of clusters is $O(n/k)$. $◀$

Thus, to show Proposition 4.7, it suffices to compute a saturated $k$-clustering. Namely:

We start with the trivial $k$-clustering, and then we saturate the clustering by exploring nodes following a standard depth-first traversal: from a node $u$, we proceed recursively on the first child $u^{\prime }$ of $u$ (if it exists) and then on the next sibling $u^{\prime \prime }$ of $u$ (if it exists). Then, we first try to merge the cluster of $u$ with the cluster of the first child $u^{\prime }$, and then try to merge the cluster of $u$ with the cluster of the next sibling $u^{\prime \prime }$. By “try to merge”, we mean that we merge the two clusters if they are mergeable.

This algorithm clearly runs in linear time as long as the mergeability tests and the actual merges are performed in constant time, which we can ensure with the right data structures. The algorithm clearly returns a clustering, and the complicated part is to show that it is saturated. For this, assume by contradiction that the result contains two mergeable clusters with LCRS-adjacent nodes $u_1$ and $u_2$: without loss of generality $u_2$ is the first child or next sibling of $u_1$. When processing $u_1$, the algorithm tried to merge the cluster that $u_1$ was in with that of $u_2$, and we know that this attempt failed because we see that $u_1$ and $u_2$ are in different clusters at the end of the algorithm. This yields a contradiction with the fact that $u_1$ and $u_2$ end up in mergeable clusters at the end of the algorithm, given the order in which the algorithm considers possible merges. $◀$

We are now ready to describe our algorithm for the dynamic evaluation problem for a fixed forest algebra $(V,H)$. Given as input a $(V,H)$-forest $F$ with $n$ nodes (without a distinguished node), we want to maintain the evaluation of $F$ (which is an element in $H$). The first step of the preprocessing is to compute in linear time an auxiliary data structure ${𝒮}_k$ which is used to maintain the evaluation of small forests under updates in $O(1)$, simply by tabulation. More precisely, ${𝒮}_k$ can be used to solve the non-restricted dynamic evaluation problem for forests of size at most $k+1$, as follows:

Letting $k≔\lfloor \log n/c_{(V,H)}\rfloor$, the first step of the preprocessing builds the data structure ${𝒮}_k$ in time $O(n)$. We then move on to the second step, which is to compute a sequence of forests by recursively clustering in the following way. We start by letting $F_0≔F$ be the input $\mathrm{\Sigma }$-forest. Then, we recursively do the following. If $|F_i|=1$ the sequence stops at $\mathrm{\ell }=i$. Otherwise, we compute a saturated $k$-clustering ${\equiv }_i$ of $F_i$ using ˜4.9, and we let $F_{i+1}$ be the forest of clusters $F_i^{}{}_{}{}^{{\equiv }_i}$. We will later show that this takes time $O(n)$ overall.

We continue with a third preprocessing step that computes the evaluation of each cluster at each level: again we will later argue that this takes $O(n)$. More precisely, we consider all the clusters $C$ of $F_0$ and add the sub-forest $F_0^C$ of $F_0$ induced by each $C$ to ${𝒮}_k$, obtaining their evaluation in time $O(|F_0|)$. We use the result of the evaluation as labels for the corresponding nodes in $F_1$. Then we add the sub-forests induced by all the clusters of $F_1$ to ${𝒮}_k$ to obtain their evaluation and to label $F_2$. We continue until we have the evaluation of $F_{\mathrm{\ell }}$. Note that none of the $(V,H)$-forests $F_i$ has a distinguished leaf: indeed, the only place where we perform non-restricted dynamic evaluation is in Proposition 4.10, i.e., on the sub-forests induced by the clusters and added to ${𝒮}_k$. Further note that all these induced sub-forests have at most $k+1$ nodes by definition of a $k$-clustering (the $+1$ comes from the $\mathrm{\square }$-labeled leaf which may be added for the border node in Definition 4.5). Now, by ˜4.6 at each step, we have that the evaluation of $F_{\mathrm{\ell }}$ is equal to the evaluation of the input $(V,H)$-forest $F_0$. This is the answer we need to maintain, and this concludes the preprocessing.

Let us now explain how we recursively handle relabeling updates. To apply an update to the node $u$ of the input forest $F_0$, we retrieve its cluster $C$ and use ${𝒮}_k$ to apply this update to $u$ to the induced sub-forest $F_0^C$ and retrieve its new evaluation, in $O(1)$. This gives us an update to apply to the node $C$ of the forest of clusters $F_1$. We continue like this over the successive levels, until we have an update applied to the single node of $F_{\mathrm{\ell }}$, which again by ˜4.6 is the desired answer. The update is handled overall in time $O(\mathrm{\ell })$, so let us bound the number $\mathrm{\ell }$ of recursion steps. At every level we have $|F_{i+1}|\le \lceil |F_i|\times (c_{V,H}/k)\rceil$ by ˜4.8 and $|F_i|\ge k$, so we have $|F_i|\le n\times ((c_{V,H}+1)/k)){}^i$ and therefore $\mathrm{\ell }=O(\log n/\log k)=O(\log n/\log \log n)$ given that $k=\lfloor \log n/c_{V,H}\rfloor$.

The only remaining point is to bound the total time needed in the preprocessing. The data structure ${𝒮}_k$ is computed in linear time in the first step. Then, we spend linear time in each $F_i$ to compute the $k$-clusterings at each level in the second step, and we again spend linear time in each $F_i$ to feed the induced sub-forests of all the clusters of $F_i$ to ${𝒮}_k$ in the third step. Now, it suffices to observe that the size of each $F_i$ decreases exponentially with $i$; for sufficiently large $n$ and $k$ we have $k\ge 2$ so $|F_i|\le |F_0|/2^i$ and the total size of the $F_i$ is $O(|F_0|)$. This ensures that the total time taken by the preprocessing across all levels in the second and third steps is in $O(n)$, which concludes.

To define almost-commutative languages, we need to define the subclasses of virtually-singleton languages and regular-commutative languages. Let us first define virtually-singleton languages via the operation of projection:

Note that virtually-singleton languages are always regular: a forest automaton can read an input forest, ignoring nodes with labels in $\mathrm{\Sigma }\setminus {\mathrm{\Sigma }}^{\prime }$, and check that the resulting forest is exactly the fixed target forest $F^{\prime }$.

Let us now define regular-commutative languages as the commutative regular forest languages, i.e., membership to the language can be determined from the Parikh image:

We can now define almost-commutative forest languages from these two classes:

Note that almost-commutative languages are always regular, because regular forest languages are closed under Boolean operations. Further, in a certain sense, almost-commutative languages generalize all word languages with a neutral letter that enjoy constant-time dynamic membership. Indeed, such languages are known by [4] and [5, Corollary 3.5] to be described by regular-commutative conditions and the presence of specific subwords on some subalphabets. Thus, letting $L$ be such a word language, we can define a forest language $L^{\prime }$ consisting of the forests $F$ where the nodes of $F$ form a word of $L$ (e.g., when taken in prefix order), and $L^{\prime }$ is then almost-commutative. As a kind of informal converse, given a $\mathrm{\Sigma }$-forest $F$, we can represent it as a word with opening and closing parentheses (sometimes called the XML encoding), and the set of such representations for an almost-commutative forest language $L^{\prime }$ will intuitively form a word language $L^{\prime }$ that enjoys constant-time dynamic membership except for the (non-regular) requirement that parentheses are balanced.

We also note that we can effectively decide whether a given forest language is almost-commutative, as will follow from the algebraic characterization in the next section:

We show the main result of this section:

This result is shown by proving the claim for regular-commutative languages and virtually-singleton languages, and then noticing that tractability is preserved under Boolean operations, simply by combining data structures for the constituent languages.

For regular-commutative languages, we maintain the Parikh image as a vector in constant-time per update, and we then easily maintain the forest algebra element to which it corresponds, similarly to the case of monoids (see [23] or [4, Theorem 4.1]).

For virtually-singleton languages, we use doubly-linked lists like in [4, Prop. 4.3] to maintain, for each letter $a$ of the subalphabet ${\mathrm{\Sigma }}^{\prime }$, the unordered set of nodes with label $a$. This allows us to determine in constant-time whether the Parikh image of the input forest restricted to ${\mathrm{\Sigma }}^{\prime }$ is correct: when this holds, then the doubly-linked lists have constant size and we can use them to recover all nodes with labels in ${\mathrm{\Sigma }}^{\prime }$. With constant-time reachability queries, we can then test if these nodes achieve the requisite forest $F^{\prime }$ over ${\mathrm{\Sigma }}^{\prime }$. $◀$

The lower bound shown in this section is conditional to a computational hypothesis on the prefix-$U_1$ problem. In this problem, we are given as input a word $w$ on the alphabet $\mathrm{\Sigma }=\{0,1\}$, and we must handle substitution updates to $w$ and queries where we are given $i\in \{1,\mathrm{\dots },|w|\}$ and must return whether the prefix of $w$ of length $i$ contains some occurrence of $1$. In other words, we must maintain a subset of integers of $\{1,\mathrm{\dots },|w|\}$ under insertion and deletion, and handle queries asking whether an input $i\in \{1,\mathrm{\dots },|w|\}$ is greater than the current minimum: note that this like a priority queue except we can only compare the minimum to an input value but not retrieve it directly. We will use the following conjecture from [4] as a hypothesis for our lower bound:

Further, our lower bound in this section will be shown for regular forest languages $L$ over an alphabet $\mathrm{\Sigma }$ which are assumed to feature a so-called neutral letter for $L$. Formally, a letter $e\in \mathrm{\Sigma }$ is neutral for $L$ if, for every forest $F$, we have $F\in L$ iff ${\pi }_{\mathrm{\Sigma }\setminus \{e\}}(F)\in L$, where $\pi$ denotes the projection operation of Definition 5.1. In other words, nodes labeled by $e$ can be removed without affecting the membership of $F$ to $L$.

We can now state the lower bound shown in this section, which is our main contribution:

The proof of Theorem 6.2 hinges on an algebraic characterization of the almost-commutative languages. Namely, we will define a class of forest algebras called ZG, by imposing the ZG equation from [4, 5]:

The intuition for the ZG equation is the following. Elements of the form $x^{\omega +1}$ in a monoid are called group elements: they are precisely the elements which span a subsemigroup (formed of the elements $x^{\omega +1},x^{\omega +2},\mathrm{\dots }$) which has the structure of a group (with $x^{\omega }=x^{2\omega }$ being the neutral element). Note that the group is always a cyclic group: it may be the trivial group, for instance in an aperiodic monoid all such groups are trivial, or in arbitrary monoids the neutral element always spans the trivial group. The equation implies that all group elements of the monoid are central, i.e., they commute with all other elements.

The point of ZG forest algebras is that they correspond to almost-commutative languages:

Proving this algebraic characterization is the main technical challenge of the paper. Let us sketch the proof of Theorem 6.4, with the details given in the full version [2].

The easy direction is to show that almost-commutative languages have a syntactic forest algebra in ZG. We first show this for commutative languages (whose vertical monoids are unsurprisingly commutative) and for virtually-singleton languages (whose vertical monoids are nilpotent, i.e., are in the class MNil of [4, 24]). We conclude because satisfying the ZG equation is preserved under Boolean operations.

The hard direction is to show that any regular language $L$ whose syntactic forest algebra is in ZG is almost-commutative, i.e., can be expressed as a finite Boolean combination of virtually-singleton and regular-commutative languages. For this, we show that morphisms to a ZG forest algebra must be determined by the following information on the input forest: which letters are rare (i.e., occur a constant number of times) and which are frequent; how many times the frequent letters appear modulo the idempotent power of the monoid; and what is the projection of the forest on the rare letters. These conditions amount to an almost-commutative language, and are the analogue for trees of results on ZG languages [4]. The proof is technical, because we must show how the ZG equation on the vertical monoid implies that every sufficiently frequent letter commutes both vertically and horizontally. $◀$

To show our conditional hardness result (Theorem 6.2), what remains is to show that the dynamic membership problem is hard for regular languages with a neutral letter and whose syntactic forest algebra is not in ZG:

We reduce from the case of words: from two contexts $v$ and $w^{\omega +1}$ witnessing that the ZG equation does not hold, we consider forests formed by the vertical composition of a sequence of contexts which can be either $v$ or $w^{\omega +1}$, with a suitable context at the beginning and end. Let $L^{\prime }$ be the word language of those sequences of contexts giving a forest in $L$: we show that the syntactic monoid of $L^{\prime }$ is not in ZG, and as $L^{\prime }$ features a neutral letter, we conclude by [4] that $L^{\prime }$ does not enjoy $O(1)$ dynamic membership assuming ˜6.1. Further, dynamic membership to $L^{\prime }$ can be achieved using a data structure for the same problem for $L$ on the forests that we constructed, so hardness also holds for $L$. $◀$

Note that Proposition 6.5 is where we use the assumption that there is a neutral letter. The result is not true otherwise, as we explain below (and will discuss further in Section 7):

With Proposition 6.5 and Theorem 6.4, we can conclude the proof of Theorem 6.2:

We already know that almost-commutative languages can be maintained efficiently (Theorem 5.5). Now, given a regular forest language $L$ which is not almost-commutative and features a neutral letter, we know by Theorem 6.4 that its syntactic forest algebra is not in ZG, so we conclude by Proposition 6.5. $◀$

Our conditional characterization of constant-time-maintainable regular languages only holds in the presence of a neutral letter. In fact, without neutral letters, it is not difficult to find non-almost-commutative forest languages with constant-time dynamic membership, e.g., the language $L_0$ from Example 6.6. There are more complex examples, e.g., dynamic membership in $O(1)$ is possible for the word language “there is exactly one $a$ and exactly one $b$, the $a$ is before the $b$, and the distance between them is even” (it is in QLZG [4]), and the same holds for the analogous forest language. We can even precompute “structural information” on forests of a more complex nature than the parity of the depths, e.g., to maintain in $O(1)$ “there is exactly one $a$ and exactly one $b$ and the path from $a$ to $b$ is a downward path that takes only first-child edges”. We also expect other constant-time tractable cases, e.g., “there is exactly one node labeled $a$ and exactly one node labeled $b$ and their least common ancestor is labeled $c$” using a linear-preprocessing constant-time data structure to answer least common ancestor queries on the tree structure [16]; or “there is a node labeled $a$ where the leaf reached via first-child edges is labeled $b$”. These tractable languages are not almost-commutative (and do not feature neutral letters), and a natural direction for future work would be to characterize the regular forest languages maintainable in $O(1)$ without the neutral letter assumption.

We have explained in Section 2 that dynamic membership is in $\mathrm{\Omega }(\log n/\log \log n)$ for some regular forest languages, and in Section 5 that it is in $O(1)$ for almost-commutative languages. One natural question is to study intermediate complexity regimes. In the setting of word languages, it was shown in [23] (and extended in [4]) that any aperiodic language $L$ could be maintained in $O(\log \log n)$ per update. This implies that some forest languages can be maintained with the same complexity, e.g., the forests whose nodes in the prefix ordering form a word in an aperiodic language $L$.

The natural question is then to characterize which forest languages enjoy dynamic membership between $O(1)$ and the general $\mathrm{\Theta }(\log n/\log \log n)$ bound. We leave this question open, but note a difference with the setting for words: there are some aperiodic forest languages (i.e., both monoids of the syntactic forest algebra are aperiodic) to which an $\mathrm{\Omega }(\log n/\log \log n)$ lower bound applies, e.g., the language for the existential marked ancestor problem reviewed at the end of Section 2. An intriguing question is whether there is a dichotomy on regular forest languages, already in the aperiodic case, between those with $O(\log \log n)$ dynamic membership, and those with a $\mathrm{\Omega }(\log n/\log \log n)$ lower bound.

Beyond relabeling updates it would be natural to study the complexity of dynamic membership under operations that can change the shape of the forest, e.g., leaf insertion and leaf deletion. Another question concerns the support for more general queries than dynamic membership, e.g., enumerating the answers to non-Boolean queries like in [19, 3] (but with language-dependent guarantees on the update time to improve over $O(\log n)$). Last, another generalization of dynamic membership to forest languages is to consider the same problem for context-free languages, e.g., for Dyck languages ([17, Proposition 1]), or for visibly pushdown languages. Note that this is a different setting from forest languages because substitution updates may change the shape of the parse tree.