diff options
| -rw-r--r-- | mgr.tex | 34 |
1 files changed, 34 insertions, 0 deletions
@@ -1073,6 +1073,40 @@ part takes constant 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)$. +\section{The full algorithm} + +As a recap we summarize all the steps of the full MSO query answering algorithm. + +\textbf{preprocessing} Take an MSO formula $\varphi(X_1, \ldots, X_k)$ and a +$\Sigma$ labeled tree $T$. + +\begin{enumerate} + \item Transform $\varphi$ and $T$ into a deterministic bottom-up automaton + $A$ and binary tree $T'$. + \item Preprocess $T'$ for computing LCA closures: + \begin{enumerate} + \item Preprocess $T'$ for LCA questions; + \item Store each vertex's in-order number. + \end{enumerate} + \item For each pair of $A$'s states, $q$ and $q'$, preprocess $T'$ for + branch infix regular questions about the language $L_{q, q'}^R$. +\end{enumerate} + +\textbf{answering questions} We receive the question ``for a a tuple of sets of +$T$'s vertices, $\vec{W}$, does $T \models \varphi(\vec{W})$?'' + +\begin{enumerate} + \item From the selection of $\vec{W}$, generate a relabeling of $T'$'s + vertices that labels vertices mentioned in $\vec{W}$ as being assigned + to the appropriate variables in $\vec{X}$. Let $W$ be this set of + relabeled vertices. + \item Compute $W'$, the smallest partition ready set containing $W$. + \item Compute the LCA parition of $T'$ with respect to $W'$. + \item In a bottom-up fashion, compute the state of $A$ running over the + relabeled tree in the roots of each part of the LCA partition. + \item Return YES if the state of $T$'s root is accepting, NO otherwise. +\end{enumerate} + \printbibliography \end{document} |