Add conclusion

1 files changed, 35 insertions, 0 deletions

diff --git a/mgr.tex b/mgr.tex
index 9f7b060..c26ae1a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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}