Add a recap of the full algorithm

1 files changed, 34 insertions, 0 deletions

diff --git a/mgr.tex b/mgr.tex
index 3ad657e..a9d75cb 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -1073,6 +1073,40 @@ part takes constant time, and there are $O(m)$ parts to handle. We did require
 $O(m \log m)$ time to sort the vertices mentioned in the question when computing
 their LCA closure, thus question answering takes time $O(m \log m)$.
 
+\section{The full algorithm}
+
+As a recap we summarize all the steps of the full MSO query answering algorithm.
+
+\textbf{preprocessing} Take an MSO formula $\varphi(X_1, \ldots, X_k)$ and a
+$\Sigma$ labeled tree $T$.
+
+\begin{enumerate}
+    \item Transform $\varphi$ and $T$ into a deterministic bottom-up automaton
+        $A$ and binary tree $T'$.
+    \item Preprocess $T'$ for computing LCA closures:
+        \begin{enumerate}
+            \item Preprocess $T'$ for LCA questions;
+            \item Store each vertex's in-order number.
+        \end{enumerate}
+    \item For each pair of $A$'s states, $q$ and $q'$, preprocess $T'$ for
+        branch infix regular questions about the language $L_{q, q'}^R$.
+\end{enumerate}
+
+\textbf{answering questions} We receive the question ``for a a tuple of sets of
+$T$'s vertices, $\vec{W}$, does $T \models \varphi(\vec{W})$?''
+
+\begin{enumerate}
+    \item From the selection of $\vec{W}$, generate a relabeling of $T'$'s
+        vertices that labels vertices mentioned in $\vec{W}$ as being assigned
+        to the appropriate variables in $\vec{X}$. Let $W$ be this set of
+        relabeled vertices.
+    \item Compute $W'$, the smallest partition ready set containing $W$.
+    \item Compute the LCA parition of $T'$ with respect to $W'$.
+    \item In a bottom-up fashion, compute the state of $A$ running over the
+        relabeled tree in the roots of each part of the LCA partition.
+    \item Return YES if the state of $T$'s root is accepting, NO otherwise.
+\end{enumerate}
+
 \printbibliography
 
 \end{document}