diff options
| -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. |