diff options
| -rw-r--r-- | mgr.tex | 14 |
1 files changed, 8 insertions, 6 deletions
@@ -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 |