diff options
| -rw-r--r-- | mgr.tex | 38 |
1 files changed, 22 insertions, 16 deletions
@@ -320,22 +320,28 @@ $\breaktable[i.q] = j - 1$. We can compute \breaktable\ in linear time with a single backwards pass through the colored graph. -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 -:= \breaktable[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' := -\breaktable[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|$. +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 +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. + +First, look at vertex $i.q_0$, 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 := \breaktable[i.q_0]$. 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$. Find the unique vertex $j.q$ in this copy of $Q$ that's colored +with $c$. $q$ is the state we will end up in, so if it is an accepting state +answer YES, if not, answer NO. + +If $k < j$, then jump to the $k$th copy of $Q$ and consider the vertex $k.q$, +the unique vertex here colored $c$. From $k.q$, follow its single outgoing edge +to $(k+1).q'$, which will be colored with color $c' < c$. Continue as we did +before, by looking at $k' := \breaktable[(k+1).q']$, 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} |