diff options
| -rw-r--r-- | mgr.tex | 59 |
1 files changed, 55 insertions, 4 deletions
@@ -475,7 +475,8 @@ next covers the whole tree). The \definedterm{subtree of $v$} is $v$ along with all its descendants. We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole -$w$} is the subtree of $v$ minus the subtree of $w$. +$w$} is the subtree of $v$ minus the subtree of $w$ (for $w$ a descendant of +$v$). For an LCA closed set $W$ in tree $T$, we define the \definedterm{LCA partition with respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees with @@ -511,8 +512,8 @@ simply the partition with respect to $W$'s LCA closure. The LCA closure of a set of $m$ vertices $W$ can be computed in time $O(m \log m)$ after linear preprocessing of the tree $T$. In the preprocessing step, in -addition to preprocessing for LCA queries, we will additionally assign each -vertex $v$ its in-order number, $IN[v]$. +addition to preprocessing for LCA queries, we will assign each vertex $v$ its +in-order number, $IN[v]$. Now to compute the closure of $W$, we first sort the vertices in $W$ with respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$ @@ -525,10 +526,60 @@ This may be proved by a simple case analysis. By the above lemma, once $W$ has been sorted by in-order numbers, we can complete our computation in time $O(m)$. It is enough to walk through the list -and issue LCA queries about neighboring pairs. +and issue LCA queries about successive pairs. \section{Computing root states of parts} +Let's now discuss how we will use LCA paritions to solve the relabel query +problem. Our approach is the following: given a query $v_1 \mapsto a_1, \ldots, +v_m \mapsto a_m$, let $W = \{ v_1, \ldots, v_m \}$. Consider the partition of +$T$ with respect to $W$. We will show how to compute $A$'s state in the root of +each part of the partition, after the tree had been relabeled. Per our +definition of the partition, we have three types of parts to consider: + +\begin{enumerate} + \item A subtree rooted at vertex $v$. + \item A singleton vertex $v$. + \item A subtree rooted at vertex $v$ with hole $w$. +\end{enumerate} + +The first case is trivial to compute: no descendants of $v$ had been relabeled, +so the states of the children of $v$ are the same as in $A$'s run on the +original tree $T$. We look them up in the precomputed run, then apply $A$'s +transition to those states and $v$'s new label. + +We will compute the states of part roots in a bottom-up fashion, so the second +case is also simple: once we've computed the states in the children of $v$, we +again simply apply $A$'s transition function to those states and $v$'s new +label. + +The third is the interesting case, that of a subtree with a hole. Consider the +path from the hole $w$ up to the root $v$. What we claim is that the question +``if $A$'s state in $w$ is $q$, is the state in $v$ going to be $q'$?'' can be +answered with a branch infix regular query. + +This is the case because a finite automaton can compute $A$'s states along the +path from $w$ to $v$ when given access to each of the node's label, state of its +children in the run of $A$ on the original labeling of $T$, and the information +whether this node is a left or right child of its parent. Thus the language +$L_{q, q'}$ over alphabet $Q \times \Sigma \times Q \times \{ left, right \}$ of +proper semgents of a run of $A$ that start in state $q$ and end in state $q'$ is +a regular language. Our algorithm for branch infix regular queries dealt with +top-down queries, but regular languages are reversible. So we preprocess $T$ for +branch infix regular queries for each language $L_{q, q'}^R$. + +Now to compute $v$'s state after the relabeling of $T$, given we've already +computed $w$'s new state $q$, take $v'$ -- $v$'s child in the direction of $w$, +find $q' \in Q$ such that the path from $v'$ to $w$ belongs to $L_{q, q'}$ +(using branch infix regular queries; since $A$ is deterministic, there will be +exactly one such $q'$), then from $q'$, the state of $v$'s other child, and +$v$'s new label, use $A$'s transition function to compute $v$'s new state. + +Since $T$'s root is the root of one of the parts of our LCA partition, in the +end we will know whether or not $A$ accepts $T$ after relabeling. Handling each +part takes constant time, and there are $O(m)$ parts to handle. We did require +$O(m \log m)$ time to sort the query's vertices when computing their LCA +closure, thus query handling takes time $O(m \log m)$. \chapter{Conclusions} |