From b4e6cc76fb81832a72413ea4cf20ff437c22f008 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Fri, 13 Aug 2021 12:02:29 -0400
Subject: Finish draft of relabeling query algorithm

---
 mgr.tex | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 55 insertions(+), 4 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 30576af..8cec592 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -475,7 +475,8 @@ next covers the whole tree).
 
 The \definedterm{subtree of $v$} is $v$ along with all its descendants.
 We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole
-$w$} is the subtree of $v$ minus the subtree of $w$.
+$w$} is the subtree of $v$ minus the subtree of $w$ (for $w$ a descendant of
+$v$).
 
 For an LCA closed set $W$ in tree $T$, we define the \definedterm{LCA partition with
 respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees with
@@ -511,8 +512,8 @@ simply the partition with respect to $W$'s LCA closure.
 
 The LCA closure of a set of $m$ vertices $W$ can be computed in time $O(m \log
 m)$ after linear preprocessing of the tree $T$. In the preprocessing step, in
-addition to preprocessing for LCA queries, we will additionally assign each
-vertex $v$ its in-order number, $IN[v]$.
+addition to preprocessing for LCA queries, we will assign each vertex $v$ its
+in-order number, $IN[v]$.
 
 Now to compute the closure of $W$, we first sort the vertices in $W$ with
 respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$
@@ -525,10 +526,60 @@ This may be proved by a simple case analysis.
 
 By the above lemma, once $W$ has been sorted by in-order numbers, we can
 complete our computation in time $O(m)$. It is enough to walk through the list
-and issue LCA queries about neighboring pairs.
+and issue LCA queries about successive pairs.
 
 \section{Computing root states of parts}
 
+Let's now discuss how we will use LCA paritions to solve the relabel query
+problem. Our approach is the following: given a query $v_1 \mapsto a_1, \ldots,
+v_m \mapsto a_m$, let $W = \{ v_1, \ldots, v_m \}$. Consider the partition of
+$T$ with respect to $W$. We will show how to compute $A$'s state in the root of
+each part of the partition, after the tree had been relabeled. Per our
+definition of the partition, we have three types of parts to consider:
+
+\begin{enumerate}
+    \item A subtree rooted at vertex $v$.
+    \item A singleton vertex $v$.
+    \item A subtree rooted at vertex $v$ with hole $w$.
+\end{enumerate}
+
+The first case is trivial to compute: no descendants of $v$ had been relabeled,
+so the states of the children of $v$ are the same as in $A$'s run on the
+original tree $T$. We look them up in the precomputed run, then apply $A$'s
+transition to those states and $v$'s new label.
+
+We will compute the states of part roots in a bottom-up fashion, so the second
+case is also simple: once we've computed the states in the children of $v$, we
+again simply apply $A$'s transition function to those states and $v$'s new
+label.
+
+The third is the interesting case, that of a subtree with a hole. Consider the
+path from the hole $w$ up to the root $v$. What we claim is that the question
+``if $A$'s state in $w$ is $q$, is the state in $v$ going to be $q'$?'' can be
+answered with a branch infix regular query.
+
+This is the case because a finite automaton can compute $A$'s states along the
+path from $w$ to $v$ when given access to each of the node's label, state of its
+children in the run of $A$ on the original labeling of $T$, and the information
+whether this node is a left or right child of its parent. Thus the language
+$L_{q, q'}$ over alphabet $Q \times \Sigma \times Q \times \{ left, right \}$ of
+proper semgents of a run of $A$ that start in state $q$ and end in state $q'$ is
+a regular language. 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 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'}$
+(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.
+
+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
+part takes constant time, and there are $O(m)$ parts to handle. We did require
+$O(m \log m)$ time to sort the query's vertices when computing their LCA
+closure, thus query handling takes time $O(m \log m)$.
 
 \chapter{Conclusions}
 
-- 
cgit v1.2.3

