From fc1f4965c581f6a3c2ec73ad1d0cafeb028fecbb Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 9 Dec 2021 15:15:08 +0100 Subject: Change some wording --- mgr.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'mgr.tex') 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 -- cgit v1.2.3