diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-10-14 16:45:53 +0200 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-10-14 16:45:53 +0200 |
commit | 350d4fb6f6368aa083d0670f712e538ced126e3c (patch) | |
tree | 282cb03c86a8cb5d6e67ca21507507a4e26f0bf5 | |
parent | f9327f40de61dc6e0ef994bc8d661fe17c096157 (diff) |
Adjust words
-rw-r--r-- | mgr.tex | 6 |
1 files changed, 3 insertions, 3 deletions
@@ -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. |