Fixup relabel query answering

1 files changed, 13 insertions, 7 deletions

diff --git a/mgr.tex b/mgr.tex
index f21bf72..899986f 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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.