From 350d4fb6f6368aa083d0670f712e538ced126e3c Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 14 Oct 2021 16:45:53 +0200 Subject: Adjust words --- mgr.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'mgr.tex') 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. -- cgit v1.2.3