m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex37
1 files changed, 31 insertions, 6 deletions
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