diff options
| -rw-r--r-- | mgr.tex | 20 |
1 files changed, 13 insertions, 7 deletions
@@ -611,7 +611,7 @@ with respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees with holes, and individual vertices created according to the following rules: \begin{enumerate} - \item If $v \in W$ is a maximal element with respect to the ancestor + \item If $v \in W$ is a maximal in $W$ with respect to the ancestor relation $<$ (i.e. there are no other elements of $W$ in the subtree of $v$), then the subtree of $v$ is a part of the partition. \item If $v \in W$ has descendants that are in $W$ only in its left subtree, @@ -628,8 +628,13 @@ with holes, and individual vertices created according to the following rules: Note that in the last rule, both $v_l$ and $v_r$ will either themselves be elements of $W$ or will have descendants in $W$ in only one of their subtrees. -Indeed, if for example $v_l$ wasn't in $W$ but it had descendants from $W$ in -both its subtrees, then $W$ wouldn't have been LCA closed. +In the first case, we will have already handled them, otherwise we will handle +them with a rule different than the last one, thus only one part will be added +to the partition for each of them. + +To see that indeed, for example $v_l$, won't need to be handled with rule 4, if +it wasn't in $W$ but had descendants from $W$ in both its subtrees, then $W$ +wouldn't have been LCA closed. Thus the partition covers the entire tree with $O(|W|)$ parts. @@ -654,9 +659,10 @@ of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$. 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 successive pairs. +Now, 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 successive pairs. By the lemma, the resulting set will indeed +contain LCAs for each pair in the set. \section{Computing root states of parts} @@ -700,7 +706,7 @@ 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'}$ +find $q' \in Q$ such that the path from $v'$ to $w$ belongs to $L_{q, q'}^R$ (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. |