m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex18
1 files changed, 10 insertions, 8 deletions
diff --git a/mgr.tex b/mgr.tex
index bda5183..86b8a54 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -703,14 +703,16 @@ the root vertices of each such component), call this data
$\componenttable[x.q]$.
For each color $c$, we will preprocess the above graph for answering questions
-of the form ``if we start in a vertex $z.q$ colored with $c$, which is the first
-copy of $Q$ on the path towards the copy of $Q$ that contains $y$?''. To achieve
-this, we create a copy of $T$ in which we mark the vertices where an edge from a
-$c$-colored vertex points to a vertex with a lower color. This tree we
-preprocess for highest marked descendant on path questions, solved in the
-previous section. Note that Figure \ref{marked-figure} is exactly the marked
-tree we create and preprocess for the green color of the colored graph in Figure
-\ref{tree-figure}.
+of the form ``given a vertex $z.q$ colored with $c$, which is the first copy of
+$Q$ on the path towards the copy of $Q$ that contains $y$ where the path from
+$z.q$ changes color?''. To achieve this, we create a copy of $T$ with a newly
+added root (thus this tree's vertices correspond to copies of $Q$ in our
+fattened tree) in which we mark the vertices corresponding to copies of $Q$
+where a non-$c$-colored vertex is pointed to by an edge from a $c$-colored
+vertex in the parent copy of $Q$. This tree we preprocess for highest marked
+descendant on path questions, solved in the previous section. Note that Figure
+\ref{marked-figure} is exactly the marked tree we create and preprocess for the
+green color of the colored graph in Figure \ref{tree-figure}.
Now question answering can proceed similar to the word case. Given a question
``does the word on vertices from $x$ down to $y$ belong to $L$?'', let $x'$ be