diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 32 |
1 files changed, 16 insertions, 16 deletions
@@ -436,16 +436,16 @@ The construction is as follows: Additionally, for each vertex $i.q$, 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 \breaktable. For example, if $i.q$ is colored with color +information in table $\breaktable$. For example, if $i.q$ is colored with color $c$, and when following the deterministic path from $i.q$, all encountered vertices are colored $c$ until $j.q'$ which is colored $c'$, then we set $\breaktable[i.q] = j - 1$. -We can compute \breaktable\ in linear time with a single backwards pass through +We can compute $\breaktable$ in linear time with a single backwards pass through the colored graph. \textbf{answering queries} Consider a query ``does $w[i, j] \in L$''. We claim that using our colored graph -and the table \breaktable\ we can, in constant time, conclude in what state the +and the table $\breaktable$ we can, in constant time, conclude in what state the automaton $A$ will end up in on the $j$th position of $w$ if it had started in its initial state on the $i$th position. @@ -513,7 +513,7 @@ This process will again lead to a coloring with the desired properties that 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 \breaktable\ table since a vertex in an internal node can have +don't have a $\breaktable$ 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$''. @@ -538,16 +538,16 @@ to handle such queries in constant time. The structure is heavily inspired by \textcite{bender2000}, where a simple algorithm for computing LCA queries is presented. -First, we create the array \posttable\ of length $n$, which is the post-order of +First, we create the array $\posttable$ of length $n$, which is the post-order of the nodes. Next, we label each node of the tree with its pre-order number. We create the -array \prefixtable\ with the corresponding pre-order labels of the nodes in -\posttable, i.e. if $\posttable[i] = v$, then $\prefixtable[i]$ is $v$'s +array $\prefixtable$ with the corresponding pre-order labels of the nodes in +$\posttable$, i.e. if $\posttable[i] = v$, then $\prefixtable[i]$ is $v$'s pre-order number. -Finally, for each node of the tree, we record its index in \posttable\ in the -array \indextable. +Finally, for each node of the tree, we record its index in $\posttable$ in the +array $\indextable$. \begin{observation} Given a node $x$ and its descendant $y$, looking at the range @@ -563,13 +563,13 @@ array \indextable. \end{enumerate} \end{observation} -The pre-order labels in \prefixtable\ are ordered according to a post-order. In +The pre-order labels in $\prefixtable$ are ordered according to a post-order. In a post-order, the root of a subtree is visited directly after all its descendants. Since $y$ is a descendant of $x$, all values between its position -in \prefixtable\ and $x$'s position there will also be descendants of $x$, +in $\prefixtable$ and $x$'s position there will also be descendants of $x$, giving item \ref{obs-descendants}. -The values in \prefixtable\ are pre-order numbers. In a pre-order, for a given +The values in $\prefixtable$ are pre-order numbers. In a pre-order, for a given node $z$, the only nodes that will have lower pre-order numbers are $z$'s ancestors, and the children of these ancestors that are to the left of the child towards $z$. By starting our range at index $\indextable[y]$, we've skipped over @@ -584,11 +584,11 @@ 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-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$ 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 marked node between $x$ and $y$. -We preprocess \prefixtable\ for RMQ queries in linear time. +We preprocess $\prefixtable$ for RMQ queries in linear time. Now when given a query $x$, $y$, we: @@ -603,7 +603,7 @@ Now when given a query $x$, $y$, we: We can detect the siutation of there not being a marked node between $x$ and $y$ during step \ref{hmd-algo-lookup} by checking if $\prefixtable[k]$ is smaller than the pre-order label of $y$. If it isn't, then all the nodes on the path -from $x$ to $y$ were unmarked (had higher values in the modified \prefixtable\ +from $x$ to $y$ were unmarked (had higher values in the modified $\prefixtable$ since values at indices corresponding to unmarked nodes are set to $\infty$), and $k$ will correspond to a marked node that's not on the path from $x$ to $y$ (or some unmarked vertex if there were no marked vertices at all in the range we @@ -643,7 +643,7 @@ 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 -\componenttable\ to see if we can answer immediately, or taking another jump +$\componenttable$ 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 by $|Q|$ since we can only jump to a lower color. Thus we can answer branch infix regular queries in constant time. |