From f86a525bbe35b5602e3ddda9092447fe5771b670 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 7 Oct 2021 14:32:32 +0200
Subject: Reword things

---
 mgr.tex | 15 +++++----------
 1 file changed, 5 insertions(+), 10 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 7074ec3..7e45d2f 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -378,9 +378,9 @@ The query problem we will solve is:
 }
 
 We begin with a similar construction as in the word case, i.e. we replace each
-vertex of the tree with a copy of the states of $A$. Call the set of $T$'s
-vertices, $V$, then our new graph has vertex set $V \times Q$, and we can refer
-to a specific vertex as $x.q$ for $x \in V$, $q \in Q$.
+vertex of the tree with a copy of the states of $A$. Our new graph has vertex
+set $V(T) \times Q$, and we can refer to a specific vertex as $x.q$ for $x \in
+V(T)$, $q \in Q$.
 
 Again, each letter $a \in \Sigma$ defines a function $a : Q \to Q$, and these
 functions induce edges in our ``fattened'' tree: consider a vertex $x$ of $T$,
@@ -415,7 +415,7 @@ subproblem.
 
 \section{Highest Marked Descendant on Path}
 
-We can now reduce the problem to the following:
+We will show that the branch infix problem reduces to the following:
 
 \queryproblem{Highest Marked Descendant on Path Queries}{%
     a tree $T$ with set $M \subseteq V(T)$ of marked vertices.
@@ -430,11 +430,6 @@ to handle such queries in constant time. The structure is heavily inspired by
 \textcite{bender2000}, where a simple algorithm for computing LCA queries is
 presented.
 
-Recall that RMQ queries can be answered in constant time after linear preprocessing of
-the input array.
-
-We turn to describing the index structure for our tree problem.
-
 First, we create the array \posttable\ of length $n$, which is the post-order of
 the nodes.
 
@@ -447,7 +442,7 @@ Finally, for each node of the tree, we record its index in \posttable\ in the
 array \indextable.
 
 \begin{observation}
-    given a node $x$ and its descendant $y$, looking at the range
+    Given a node $x$ and its descendant $y$, looking at the range
     $\prefixtable[\indextable[y], \indextable[x] - 1]$, all the values in this
     range are descendants of $x$, and the values smaller than
     $\prefixtable[\indextable[y]]$ correspond to ancestors of $y$.  In
-- 
cgit v1.2.3

