diff options
| -rw-r--r-- | mgr.tex | 35 |
1 files changed, 35 insertions, 0 deletions
@@ -1165,6 +1165,41 @@ $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} + +\section{Complexities with respect to formulae and automata} + +In our algorithms in Section \ref{wordinfix} and Chapters \ref{branchinfix} and +\ref{mso-query-answering} we treated the MSO formula or automaton (over words or +trees) that needed to be handled as a fixed parameter to our algorithms, and +didn't analyze how they impact time complexities. Let's quickly perform this +analysis now. + +The MSO to automaton formula reduction implied by Theorem \ref{mso-to-automaton} +is unfortunately non-elementary, making MSO query answering non-elementary with +respect to $|\varphi|$. The situation improves if we start with a relabel +regular questions problem directly, rather than needing to reduce from an MSO +formula. The branch infix regular questions problem itself, which we use as a +subalgorithm when answering relabel questions, behaves very well when given a +deterministic automaton on input. To answer branch infix regular questions about +a tree $T$ and deterministic automaton $A$ we need to create $|Q|$ copies of +$T$ for highest marked descendant questions, one for each color (and there are +$|Q|$ colors). When answering a question, we will make at most $|Q|$ jumps, each +jump itself taking constant time. Thus, using our notation for algorithms with a +preprocessing phase, branch infix regular questions have an +\qptime{$O(|A||T|$)}{$O(|A|)$} algorithm. Relabel regular queries themselves will +unfortunately work in exponential time: recall that the languages we preprocess +for branch infix questions for are constructed by \textit{reversing} a +deterministic automaton's language. This is a procedure that requires +determinization of a nondeterministic automaton, and thus can explode +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}. + \printbibliography \end{document} |