diff options
| -rw-r--r-- | mgr.tex | 5 |
1 files changed, 4 insertions, 1 deletions
@@ -1037,9 +1037,12 @@ the current vertex's left or right child. The automaton works as follows: \item Accept if the final tree state is $q'$. \end{enumerate} +This automaton recognizes exactly $L_{q,q'}$, by performing essentially the same +computation we described before. This completes the proof of the lemma. + Our algorithm for branch infix regular queries dealt with top-down queries, but regular languages are reversible. So we preprocess $T$ for branch infix regular -queries for each language $L_{q, q'}^R$. Now a query about whether the word on +queries for each language $L_{q, q'}^R$. A question about whether the word on the path from $x$ down to $y$ belongs to $L_{q, q'}^R$ is the same as asking if the word from $y$ up to $x$ belongs to $L{q,q'}$. Note that the number of languages we need to preprocess for is constant in the size of the tree -- it |