Begin describing relabel queries solution

2 files changed, 78 insertions, 2 deletions

diff --git a/definitions.sty b/definitions.sty
index cbe36f2..1105fb3 100644
--- a/definitions.sty
+++ b/definitions.sty
@@ -18,3 +18,5 @@
 \newcommand{\qpoptimal}{\qptime{$O(n)$}{$O(1)$}}
 
 \newcommand{\definedterm}[1]{\emph{#1}}
+
+\newcommand{\mathlca}{\mathit{LCA}}
diff --git a/mgr.tex b/mgr.tex
index cd44d87..30576af 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -453,8 +453,82 @@ jump takes constant time, and the number of jumps is bounded $|Q|$ since we can
 only jump to a lower color. Thus we can answer branch infix regular queries in
 constant time.
 
-\chapter{Relabel Regular Queries on Trees}
-h
+\chapter{MSO Query Answering on Trees}
+
+\section{Relabel Regular Queries on Trees}
+
+Fix a tree automaton $A$ and take a $\Sigma$-labeled binary tree $T$.
+
+We'll preprocess the tree in such a way that when given a relabel query, we'll
+be able to partition the tree into linearly (with respect to the query's size)
+many parts, then, in a bottom-up fashion, compute the state in the root of each
+part in the relabeled tree. The computation for each part will take constant
+time.
+
+\subsection{LCA partition}
+
+Consider a set of tree vertices $W$. We'll say that $W$ is \definedterm{LCA
+closed} if for every pair of vertices $v, w \in W$, it is the case that
+$\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their LCA). We also
+require that the tree's root is in $W$ (just to ensure the partition we define
+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$.
+
+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
+holes, and individual vertices created according to the following rules:
+
+\begin{enumerate}
+    \item If $v \in W$ is a maximal element with respect to the ancestor
+        relation $<$ (i.e. there are no other elements of $W$ in the subtree of
+        $v$), then the subtree of $v$ is a part of the partition.
+    \item If $v \in W$ has descendants that are in $W$ only in its left subtree,
+        let $w$ be the highest such descendant (there is a unique highest
+        descendant because $W$ is LCA closed). The subtree of $v$ with hole $w$
+        is a part of the partition.
+    \item Symmetrically if $v \in W$ only has descendants that are in $W$ in its
+        right subtree.
+    \item If $v \in W$ has descendants that are in $W$ in both its subtrees, let
+        $v_l$ and $v_r$ be $v$'s left and right child, respectively. Treat $v_l$
+        and $v_r$ as if they were in $W$ for the purposes of defining the
+        partition. Put $v$ into a singleton part on its own.
+\end{enumerate}
+
+Note that in the last rule, both $v_l$ and $v_r$ will either themselves be
+elements of $W$ or will have descendants in $W$ in only one of their subtrees.
+Indeed, if for example $v_l$ wasn't in $W$ but it had descendants from $W$ in
+both its subtrees, then $W$ wouldn't have been LCA closed.
+
+Thus the partition covers the entire tree with $O(|W|)$ parts.
+
+If $W$ is not LCA closed, we will call the LCA partition with respect to $W$
+simply the partition with respect to $W$'s LCA closure.
+
+\subsection{Computing the 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]$.
+
+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$
+of vertices such that $IN[v_1] < \ldots < IN[v_m]$.
+
+Lemma: if $IN[u] < IN[v] < IN[w]$, then $\mathlca(u, w)$ is equal to either
+$\mathlca(u, v)$ or $\mathlca(v, w)$.
+
+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.
+
+\section{Computing root states of parts}
+
 
 \chapter{Conclusions}