From cb614b7456dade96de346a53f4873c7db23b92ba Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Tue, 7 Dec 2021 13:32:21 +0100 Subject: Finalize subtree with hole explanation --- mgr.tex | 14 ++++++++------ 1 file 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 -- cgit v1.2.3