diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 69 |
1 files changed, 42 insertions, 27 deletions
@@ -55,14 +55,15 @@ We define relabel regular questions on trees, which, via the known equivalence between tree automata and MSO formulae on trees, happens to be a generalization of the MSO query answering problem on trees. We show these - questions can be answered in time $O(m \log(m))$ with respect to question - size (constant time in the case of MSO formulae with only first-order free - variables) after preprocessing the input tree in linear time. Along the way, - we show an algorithm for answering questions of the form ``Does the infix of - a tree branch between nodes $x$ and $y$ belong to the regular language $L$'' - (for a previously fixed regular language $L$) in constant time after linear - preprocessing. Our approach is much simpler in presentation than if using - deterministic factorization forests due to \textcite{colcombet}. + questions can be answered in time $O_{\varphi}(m \log(m))$ with respect to + question size (constant time in the case of MSO formulae with only + first-order free variables) after preprocessing the input tree in time linear + with respect to the tree's size. Along the way, we show an algorithm for + answering questions of the form ``Does the infix of a tree branch between + nodes $x$ and $y$ belong to the regular language $L$'' (for a previously + fixed regular language $L$) in constant time after linear preprocessing. Our + approach is much simpler in presentation than if using deterministic + factorization forests due to \textcite{colcombet}. \end{abstract} \tableofcontents @@ -90,7 +91,12 @@ trees. While MSO model checking is NP-hard in general, \textcite{courcelle1990} showed that deciding if an MSO sentence holds in a structure of bounded treewidth can be done in time linear in the size of the structure. This, using the naive method described above, gives us an algorithm for MSO query answering -over trees that answers each question in time $O(n)$ ($n$ being the size of the +over trees that answers each question in time +$O_{\varphi}(n)$\footnote{Throughout the text we use $O_{x}(f(n))$ notation, +where $x$ is some portion of an algorithm's input. It indicates $x$ as a +parameter of the algorithm, i.e. that for every integer $k$, there is some +constant $c_k$ such that if $|x| = k$, then the algorithm runs in time $c_k +f(n)$ ($n$ being the size of the remaining input).} ($n$ being the size of the tree). In our setting we suppose that we want to answer multiple such questions about a @@ -100,21 +106,22 @@ algorithm could be improved with Amarilli et al.'s \cite{amarilli2019} data structure that allows updates of the underlying tree. Let $m$ be the size of a given question, i.e. $m = |W_1 \cup \ldots \cup W_k|$. Amarilli's result allows us to preprocess the tree in linear time, label it with a choice of $W_1, -\ldots, W_k$ in time $O(m \log n)$, then answer model checking in constant time, -thus greatly improving over the naive algorithm for questions that talk about a -small number of vertices compared to the size of the whole tree. +\ldots, W_k$ in time $O_{\varphi}(m \log n)$, then answer model checking in +constant time, thus greatly improving over the naive algorithm for questions +that talk about a small number of vertices compared to the size of the whole +tree. \section{Main result} -We will improve on the above method even further showing an algorithm that, -after linear preprocessing of the tree we can answer questions in time +We will improve on the above method even further, showing an algorithm with +which, after linear preprocessing of the tree, we can answer questions in time linearithmic with respect to the question size. In particular, we eliminate any dependence on tree size during question answering. More explicitly, we will show how to solve Problem \ref{mso-query-answering-problem}, with a preprocessing algorithm working in -time $O(n)$ (where $n$ is the size of the input tree), and then answer questions -in time $O(m \log m)$ (where $m$ is the size of the question): +time $O_{\varphi}(n)$ (where $n$ is the size of the input tree), and then answer questions +in time $O_{\varphi}(m \log m)$ (where $m$ is the size of the question): \queryproblem[% an MSO formula $\varphi(\vec{X})$ over trees with $k$ free @@ -202,6 +209,10 @@ The rest of our work is organized in the following way: compute the LCA closure of a set of $m$ vertices of a preprocessed tree in time $O(m \log m)$. \end{itemize} + \item In Chapter \ref{conclusion} we offer some concluding remarks, + including discussion of time complexities with respect to parameters, + which we mostly ignore throughout the main text, and a generalization of + our result to structures of bounded treewidth. \end{itemize} \chapter{Preliminaries}\label{preliminaries} @@ -745,15 +756,18 @@ can formulate as Theorem \ref{mso-query-answering-theorem}: \begin{theorem}\label{mso-query-answering-theorem} Problem \ref{mso-query-answering-problem} can be solved in time - \qptime{$O(n)$}{$O(m \log m)$}. + \qptime{$O_{\varphi}(n)$}{$O_{\varphi}(m \log m)$}. Furthermore, time + complexity with respect to the size of the tree automaton is exponential in + both the preprocessing and question answering phases. \end{theorem} First, let's reduce Problem \ref{mso-query-answering-problem} to Problem \ref{relabel-regular-queries}: \begin{lemma} - If Problem \ref{relabel-regular-queries} has an \qptime{$O(n)$}{$O(m \log - m)$} solution, then so does Problem \ref{mso-query-answering-problem}. + If Problem \ref{relabel-regular-queries} has an \qptime{$O_A(n)$}{$O_A(m + \log m)$} solution, then Problem \ref{mso-query-answering-problem} has an + \qptime{$O_{\varphi}(n)$}{$O_{\varphi}(m \log m)$} one. \end{lemma} Proof: We proceed with several standard linear reductions that transform Problem @@ -802,7 +816,7 @@ This concludes the proof of the lemma, and Theorem \begin{theorem}\label{relabel-regular-queries-theorem} Problem \ref{relabel-regular-queries} can be solved in time - \qptime{$O(n)$}{$O(m \log m)$}. + \qptime{$O_A(n)$}{$O_A(m \log m)$}. \end{theorem} The rest of this chapter is dedicated to proving Theorem @@ -820,7 +834,7 @@ take constant time. Partitioning into the $O(m)$ parts we're interested in will take time $O(m \log m)$, then after the bottom-up computation we will arrive at the root's state in -time $O(m)$, thus answering the question in the promised time. +time $O_A(m)$, thus answering the question in the promised time. \subsection{LCA partition} @@ -1168,9 +1182,9 @@ new label, use $A$'s transition function to compute $v$'s new state. Since $T$'s root is the root of one of the parts of our LCA partition, in the end we will know whether or not $A$ accepts $T$ after relabeling. Handling each -part takes constant time, and there are $O(m)$ parts to handle. We did require +part takes $O_A(1)$ 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)$. +their LCA closure, thus question answering takes time $O_A(m \log m)$. \section{The full algorithm} @@ -1206,7 +1220,7 @@ $T$'s vertices, $\vec{W}$, does $T \models \varphi(\vec{W})$?'' \item Return YES if the state of $T$'s root is accepting, NO otherwise. \end{enumerate} -\chapter{Conclusion} +\chapter{Conclusion}\label{conclusion} \section{Complexities with respect to formulae and automata} @@ -1237,9 +1251,10 @@ exponentially. \section{Structures of bounded treewidth} -With our algorithm we get, ``for free'', an \qptime{$O(n)$}{$O(m \log m)$} algorithm -for MSO query answering on structures of bounded treewidth. Indeed, bounded -treewidth structures are MSO interpretable in linear time \cite{courcelle1992}. +With our algorithm we get, ``for free'', an +\qptime{$O_{\varphi}(n)$}{$O_{\varphi}(m \log m)$} algorithm for MSO query +answering on structures of bounded treewidth. Indeed, bounded treewidth +structures are MSO interpretable in linear time \cite{courcelle1992}. \printbibliography |