From 846ec3bd7829fee41fdc815705bbf623f001a0ed Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 16 Dec 2021 17:34:43 +0100 Subject: Fix branch infix preprocessing --- mgr.tex | 18 ++++++++++-------- 1 file 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 -- cgit v1.2.3