m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex5
1 files changed, 4 insertions, 1 deletions
diff --git a/mgr.tex b/mgr.tex
index 015e0ef..0859df8 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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