diff options
| -rw-r--r-- | mgr.tex | 69 |
1 files changed, 66 insertions, 3 deletions
@@ -328,9 +328,38 @@ The query problem we will solve is: the path from $x$ to $y$ belong to $L$? } -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 +We begin with a similar construction as in the word case, i.e. we replace each +vertex of the tree with a copy of the states of $A$, $Q$. Again, each letter +defines a function $a : Q \to Q$, and these functions induce edges in our +``fattened'' tree: if $A$ in state $q$, reading letter $a$ goes to $q'$, then a +copy of $Q$ corresponding to an internal node of $T$ will have edges going to +$q'$ in all of the copies of $Q$ corresponding to the children of this node in +$T$. + +We also color all vertices with $1, \ldots, |Q|$ in this graph, analogously to +how we did so in the word case: begin by coloring an arbitrary vertex in the +root with $1$, then follow edges downwards, coloring all visited vertices with +$1$. Then begin the same process with the next color, restarting with a +different vertex in a given copy of $Q$ if we run into an already colored +vertex. + +This process will again lead to a coloring with the desired properties that + +\begin{enumerate} + \item every copy of $Q$ has one vertex of each of the $|Q|$ colors; + \item when a vertex of color $i$ has an edge to a vertex of color $j$ in a + child copy of $Q$, then $i \geq j$. +\end{enumerate} + +Now let's consider how we could answer a query ``is the branch infix from $x$ +down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We +don't have a $BREAK$ table since a vertex in an internal node can have +arbitrarily many points below it where its color is broken by a lower one. +Somehow we need to be able to find such a break point that is ``in the direction +of $y$ from $x$''. + +In the next section we formulate this question formally and solve it as a +subproblem. \section{Highest Marked Descendant on Path} @@ -390,6 +419,40 @@ Now when given a query $x$, $y$, we: answer to our query. \end{enumerate} +\section{Solving branch infix regular queries} + +With the above problem solved, we are ready to finish our solution to the branch +infix regular query problem. Recall that we have replaced the input tree $T$'s +vertices with copies of $Q$, then connected and colored them in the same way as +in the word case. We additionally remember in each vertex a unique identifier of +the connected component of vertices of the same color that it's in (call this +data $COMPONENT[v]$). + +For each color $c$, we will preprocess the above graph for queries that answer +the question ``if we start in a vertex $v$ colored with $c$, which is the first +copy of $Q$ on the path towards the copy of $Q$ that contains $y$?'' by creating +a copy of $T$ in which we mark the vertices where an edge from a $c$ colored +vertex points to a vertex with a lower color. This tree we preprocess for the +queries from the previous section. + +Now query answering can proceed similar to the word case. Given a query ``does +the word on vertices from $x$ down to $y$ belong to $L$?'' find the copy of $Q$ +corresponding to $x$ and consider the color $c$ corresponding to the initial +state here. If in the copy of $Q$ corresponding to $y$, the vertex of color $c$ +has the same $COMPONENT$ information as the initial state we were considering, +we can immediately answer whether or not $A$ will accept the word on this path +based on whether this state is accepting. + +Otherwise, we need to jump down to a lower copy of $Q$. We do this by issuing a +highest marked descendant on path query on the marked tree we created for color +$c$. The answer to this query exactly corresponds to the point where the path of +color $c$ from our initial state merges into a lower color $c'$ on the path +towards $y$. From here we continue as at the beginning, checking $COMPONENT$ to +see if we can answer immediately, or taking another jump down. Handling each +jump takes constant time, and the number of jumps is bounded $|Q|$ since we can +only jump to a lower color. Thus we can answer branch infix regular queries in +constant time. + \chapter{Relabel Regular Queries on Trees} h |