Expand sections

1 files changed, 40 insertions, 18 deletions

diff --git a/mgr.tex b/mgr.tex
index c13ccc1..362cc45 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -227,10 +227,19 @@ problems.
 As mentioned above, \textcite{bender2000} show an \qpoptimal{}
 algorithm for the RMQ problem.
 
-\subsection{Word infix regular queries}
+Their method is as follows. First they show that a special case of the RMQ
+problem, $\pm1$ RMQ, can be solved in \qpoptimal. This restriction of the problem
+is enough to handle LCA queries. Then, for the general RMQ case, a Cartesian
+tree\footnote{A Cartesian tree of a list is a binary tree with the list's
+minimum element in its root, the root's children being Cartesian trees of the
+left and right sublists around the minimal element. It can be constructed in
+linear time.} of the list is built, and LCA queries on this tree correspond to
+range minimum queries on the list.
+
+\subsection{Word infix regular queries}\label{wordinfix}
 
 \queryproblem[%
-    regular language $L$ over alphabet $\Sigma$.
+    regular language $L$ over alphabet $\Sigma$, given by DFA $A$.
 ]{Word Infix Regular Queries}{%
     a word $w \in \Sigma^*$.
 }{%
@@ -238,14 +247,11 @@ algorithm for the RMQ problem.
     j]$ belong to $L$?
 }
 
-There is a simple and well-known data structure that, given a fixed automaton
-$A$, preprocesses an input word $w$ in time $O(n)$, and afterwards is able to
-answer in time $O(1)$ questions of the form ``Is the infix $w[i, j]$ accepted by
-$A$?''. We present the full construction as we will be generalizing its
-internals for the tree case in \Ref{branchinfix}.
+This problem has a very elegant \qpoptimal{} solution. We present the full
+construction as we will be generalizing its internals for the tree case in
+Chapter \ref{branchinfix}.
 
-Take $A$ that is deterministic. We begin by replacing each letter of $w$ with
-the set of states of $A$, $Q$.
+We begin by replacing each letter of $w$ with the set of states of $A$, $Q$.
 
 Each letter $a$ of $w$ defines an injective function on $Q$, and we draw these
 functions as directed edges between successive copies of $Q$. For example, if
@@ -282,12 +288,33 @@ The construction is as follows:
     \item Repeat steps 3.-5. for each successive color up to $|Q|$.
 \end{enumerate}
 
-Additionally, in each vertex, we store the index of the next copy of $Q$ in
-which the path of this vertex's color is broken by a lower color.
+Additionally, for each vertex $v$, we store the index of the next copy of $Q$ in
+which the path of this vertex's color is broken by a lower color. Put this
+information in table $BREAK$.
+
+To handle the query ``does $w[i, j] \in L$'', we look at vertex $v$, which is
+the vertex of $A$'s
+initial state in the $i$th copy of $Q$ and note its color $c$. Now we want to
+answer the following question: if we follow the edges of the graph until the
+$j$th copy of $Q$, what color will we end in? First, look at $k := BREAK[v]$. If
+$k \geq j$, then we know that in the $j$th copy of $Q$, the path we're interested
+in still has color $c$. Look at the state in this copy of $Q$ that's colored
+with $c$, if it's an accepting state answer YES, if not, answer NO.
+
+If $k < j$, then jump to the $k$th copy of $Q$ and take the edge from the vertex
+colored $c$ here to the next copy of $Q$. The vertex $v'$ we end up in will be
+colored with color $c' < c$. Continue as we did before, by looking at $k' :=
+BREAK[v']$, comparing it to $j$, and either halting if $k' \geq j$, or jumping
+again otherwise. Because with each jump we move to a color strictly smaller than
+before, the number of jumps is bounded by the number of colors, $|Q|$. Thus the
+query is answered in time constant with respect to $|w|$.
 
 \chapter{Branch Infix Regular Queries}\label{branchinfix}
 
-In this chapter we will present a solution to the following query problem:
+Before solving our main problem, that of MSO queries on trees, we generalize
+word infix regular queries (section \ref{wordinfix}) to trees. This will be a
+vital step in the MSO queries algorithm, but is an interesting result on its own
+so it deserves its own chapter.
 
 \queryproblem[%
     regular language $L$ over alphabet $\Sigma$.
@@ -298,16 +325,11 @@ In this chapter we will present a solution to the following query problem:
     the path from $x$ to $y$ belong to $L$?
 }
 
-\section{Generalizing to trees}
-
-We generalize the above construction from regular infix queries on a
-word, to ones on a tree.
-
 We begin with similar path coloring as in the word case, i.e. we replace each
 vertex of the tree with a copy of the states of $A$, $Q$. Each labeled node
 defines
 
-\section{Highest Black Descendant on Path}
+\section{Highest Marked Descendant on Path}
 
 We can now reduce the problem to the following: