m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex58
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: