diff options
| -rw-r--r-- | mgr.tex | 37 |
1 files changed, 31 insertions, 6 deletions
@@ -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 |