diff options
| -rw-r--r-- | mgr.tex | 11 |
1 files changed, 6 insertions, 5 deletions
@@ -1055,11 +1055,12 @@ computation we described before. This completes the proof of the lemma. Our algorithm for branch infix regular questions dealt with top-down questions (i.e. the word we ask about runs from a higher vertex down to its descendant). Regular languages are reversible, so we can preprocess $T$ for branch infix -regular questions 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 -only depends on the size of the automaton. +regular questions for each language $L_{q, q'}^R$ (where $\cdot^R$ denotes the +reversed language). 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 only depends on the +size of the automaton. 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$, |