From e18ebee607ce8a02dd98d432e528fe0f9d8da8e0 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 14 Oct 2021 14:37:42 +0200
Subject: Describe organization of paper

---
 mgr.tex | 37 +++++++++++++++++++++++++++++++------
 1 file changed, 31 insertions(+), 6 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index d780602..8232e59 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -109,14 +109,14 @@ in time $O(m \log m)$ (where $m$ is the size of the query):
     an MSO formula $\varphi(\vec{X})$ over trees with $k$ free
     second-order variables.
 ]{%
-    MSO Query Answering on Trees
+    \label{mso-query-answering-problem} MSO Query Answering on Trees
 }{%
     a tree $T$.
 }{%
     given a $k$-tuple of subsets of $T$'s vertices $\vec{W}
     \in \mathcal{P}(V(T))^{k}$, is $\vec{W}$ a satisfying assignment to
     $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$?
-}\label{mso-query-answering-problem}
+}
 
 Though we speak about MSO formulae with second-order variables only, first-order
 variables are also supported simply by restricting to queries in which sets
@@ -131,7 +131,7 @@ the following problem about tree automata, which we solve in Chapter
 \queryproblem[%
     a deterministic bottom-up tree automaton $A$ over ranked alphabet $\Sigma$.
 ]{%
-    Relabel Regular Queries on Trees
+    \label{relabel-regular-queries} Relabel Regular Queries on Trees
 }{%
     a tree $T$ labeled with $\Sigma$.
 }{%
@@ -172,7 +172,32 @@ Chapter \ref{branchinfix}. However, Colcombet's factorization depends on fairly
 deep and complex applications of semigroup theory. We present a much more
 straightforward algorithmic approach.
 
-\chapter{Preliminaries}
+\section{Organization}
+
+The rest of our work is organized in the following way:
+
+\begin{itemize}
+    \item In Chapter \ref{preliminaries} we introduce definitions and
+        existing algorithms we will use to arrive at our main result.
+        \begin{itemize}
+            \item In particular, Section \ref{query-answering-problems} serves
+                as a short review of some fundamental algorithms for solving
+                query answering problems related to trees and regular languages.
+        \end{itemize}
+    \item In Chapter \ref{branchinfix} we solve an important subproblem, which
+        is a generalization of a well known algorithm about words to the tree
+        case.
+    \item In Chapter \ref{mso-query-answering} we arrive at our main result by
+        reducing Problem \ref{mso-query-answering-problem} to Problem
+        \ref{relabel-regular-queries} and solving it.
+        \begin{itemize}
+            \item Of note, in Section \ref{computing-closure} we show how to
+                compute the LCA closure of a set of $m$ tree vertices in time
+                $O(m \log m)$.
+        \end{itemize}
+\end{itemize}
+
+\chapter{Preliminaries}\label{preliminaries}
 
 \section{Definitions}
 \subsection{Trees}
@@ -269,7 +294,7 @@ We note that the converse of this theorem is also true (i.e. that for every tree
 automaton, there is a corresponding MSO formula), however we will use only the
 MSO to automata direction in this work.
 
-\section{Query answering problems}
+\section{Query answering problems}\label{query-answering-problems}
 
 Consider a computational problem whose inputs are of the form $(S, q) \in
 \mathcal{S} \times Q$ for some set of \definedterm{structures} $\mathcal{S}$ and
@@ -714,7 +739,7 @@ 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}
+\subsection{Computing the LCA closure}\label{computing-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
-- 
cgit v1.2.3

