From b446d37d892a78c44fbde479d805e7f062b8df3a Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 14 Oct 2021 16:56:18 +0200
Subject: Reword and add notes
---
mgr.tex | 17 +++++++++++------
1 file 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}
--
cgit v1.2.3