diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 48 |
1 files changed, 26 insertions, 22 deletions
@@ -503,37 +503,41 @@ check). \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 $\componenttable[v]$). +With the above problem solved, we are ready to finish our algorithm for 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 is +in (call this data $\componenttable[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. +vertex points to a vertex with a lower color. This tree we preprocess for +highest marked descendant on path queries. 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 \componenttable\ 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 +the word on vertices from $x$ down to $y$ belong to $L$?'' look at the vertex +$x.q_0$ and consider its color $c$. In the copy of $Q$ corresponding to $y$ +consider the vertex $y.q$, the unique vertex here of color $c$. If it is in the +same connected component as $x.q_0$ (which we check by comparing +$\componenttable[x.q_0]$ with $\componenttable[y.q]$), we can immediately answer +whether or not $A$ will accept the word on this path based on whether this state +is accepting. Since we have not changed connected components, there is a +single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed the state $A$ +would have ended in after running on the word from $x$ down to $y$. + +Otherwise, we need to jump down to a lower copy of $Q$. We can find the first +such copy where the color on our path changes from $c$ to something lower 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 \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 -$|Q|$ since we can only jump to a lower color. Thus we can answer branch infix -regular queries in constant time. +by $|Q|$ since we can only jump to a lower color. Thus we can answer branch +infix regular queries in constant time. \chapter{MSO Query Answering on Trees} |