diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 16 insertions, 0 deletions
@@ -1285,6 +1285,22 @@ With our algorithm we get, ``for free'', an answering on structures of bounded treewidth. Indeed, bounded treewidth structures are MSO interpretable in trees in linear time \cite{courcelle1992}. +\section{LCA closure question answering} + +In Section \ref{computing-closure} we showed that the following question answering +problem +\queryproblem{LCA closure question answering}{% + a tree $T$. +}{% + given a set of tree vertices $S$, compute the LCA closure of $S$. +} +has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. An open question is whether +this is an optimal solution. If the question answering step's complexity could +be reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth +would then be known to be in \lineardelaylin. Or is there a lower bound on +computing LCA closures in this setting, for example, would it be possible to +reduce comparison sorting to computing LCA closures? + \printbibliography \end{document} |