Finalize subtree with hole explanation

1 files changed, 8 insertions, 6 deletions

diff --git a/mgr.tex b/mgr.tex
index 1c1644b..015e0ef 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -1041,14 +1041,16 @@ 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
 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'}$.
+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
+only depends on the size of the automaton.
 
-Now to compute $v$'s state after the relabeling of $T$, given we've already
-computed $w$'s new state $q$, take $v'$ -- $v$'s child in the direction of $w$,
-find $q' \in Q$ such that the path from $v'$ to $w$ belongs to $L_{q, q'}^R$
+Given the subtree of $x$ with hole $y$, once we've computed $y$'s new state $q$,
+to compute $x$'s new state, take $x'$ -- $x$'s child in the direction of $y$,
+find $q' \in Q$ such that the path from $x'$ to $y$ belongs to $L_{q, q'}^R$
 (using branch infix regular queries; since $A$ is deterministic, there will be
-exactly one such $q'$), then from $q'$, the state of $v$'s other child, and
-$v$'s new label, use $A$'s transition function to compute $v$'s new state.
+exactly one such $q'$). Now from $q'$, the state of $x$'s other child, and
+$x$'s new label, use $A$'s transition function to compute $x$'s new state.
 
 Since $T$'s root is the root of one of the parts of our LCA partition, in the
 end we will know whether or not $A$ accepts $T$ after relabeling. Handling each