From d3a975403172ae848aaab98c4894442627edb6f0 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 18:02:29 +0100 Subject: Add conclusion --- mgr.tex | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) 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} -- cgit v1.2.3