diff options
| -rw-r--r-- | mgr.tex | 58 |
1 files changed, 40 insertions, 18 deletions
@@ -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: |