Reword and add notes

1 files changed, 11 insertions, 6 deletions

diff --git a/mgr.tex b/mgr.tex
index e88115c..215540a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -632,9 +632,10 @@ consider the vertex $y.q$, the unique vertex here of color $c$. If it is in the
 same connected component as $x.q_0$ (which we check by comparing
 $\componenttable[x.q_0]$ with $\componenttable[y.q]$), we can immediately answer
 whether or not $A$ will accept the word on this path based on whether this state
-is accepting. Since we have not changed connected components, there is a
-single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed the state $A$
-would have ended in after running on the word from $x$ down to $y$.
+is accepting. If that is the case then we have not changed connected components,
+thus there is a single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed
+the state $A$ would have ended in after running on the word given by the labels
+from $x$ down to $y$.
 
 Otherwise, we need to jump down to a lower copy of $Q$. We can find the first
 such copy where the color on our path changes from $c$ to something lower by
@@ -736,9 +737,11 @@ 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.
-In the first case, we will have already handled them, otherwise we will handle
+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 the partition for each of them. In particular, each element of $W$ will
+contribute only a constant number of parts to the partition (one part if handled
+with one of the first three rules, three parts if handled with the last one).
 
 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$
@@ -770,7 +773,9 @@ This may be proved by a simple case analysis.
 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.
+contain LCAs for each pair in the set. Note also that for each successive pair
+we will have added at most one new vertex to the closure, thus the size of the
+closure of $W$ is linear in $m$.
 
 \section{Computing root states of parts}