m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:53 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:53 +0200
commit350d4fb6f6368aa083d0670f712e538ced126e3c (patch)
tree282cb03c86a8cb5d6e67ca21507507a4e26f0bf5
parentf9327f40de61dc6e0ef994bc8d661fe17c096157 (diff)
Adjust words
-rw-r--r--mgr.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/mgr.tex b/mgr.tex
index 9aa3d92..5ccc072 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -277,7 +277,7 @@ automata.
\subsection{Monadic Second Order (MSO) Logic}
% def of MSO
-From a logical point of view, the trees we work with can be seen as structures
+From a logic point of view, the trees we work with can be seen as structures
over a signature with a single binary relation $E$ and unary relations $U_a$ for
each $a \in \Sigma$. $E(v, w)$ represents a (directed from parent to child) edge
from $v$ to $w$. $U_a(v)$ signifies that $v$'s label is $a$.
@@ -581,12 +581,12 @@ Items \ref{obs-descendants} and \ref{obs-ancestors} together give us item
\ref{obs-conclusion}.
In our problem, we only care about ancestors of $y$ that are marked. So
-we perform one final modification of our data structure: for all non-black
+we perform one final modification of our data structure: for all non-marked
vertices $v$, we change $\prefixtable[\indextable[v]]$ to $\infty$ (which can be
represented by $n+1$, an integer greater than any node's pre-order label). With
\prefixtable\ modified like this, we observe that now the minimum value of
$\prefixtable[\indextable[y], \indextable[x] - 1]$ corresponds exactly to the
-answer of our queries -- the highest black node between $x$ and $y$.
+answer of our queries -- the highest marked node between $x$ and $y$.
We preprocess \prefixtable\ for RMQ queries in linear time.