diff options
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 9 insertions, 7 deletions
@@ -120,8 +120,9 @@ dependence on tree size during question answering. More explicitly, we will show how to solve Problem \ref{mso-query-answering-problem}, with a preprocessing algorithm working in -time $O_{\varphi}(n)$ (where $n$ is the size of the input tree), and then answer questions -in time $O_{\varphi}(m \log m)$ (where $m$ is the size of the question): +time $O_{\varphi}(n)$ (where $n$ is the size of the input tree), and then answer +questions in time $O_{\varphi}(m \log m)$ (where $m$ is the size of the +question): \queryproblem[% an MSO formula $\varphi(\vec{X})$ over trees with $k$ free @@ -848,8 +849,9 @@ $W \subseteq V(T)$ is \definedterm{partition ready} if \begin{enumerate} \item it is LCA closed; \item it contains the root of the tree; - \item\label{both-subtrees-property} for every $v \in W$, either it has descendants in $W$ in at most one - of its subtrees, or both of its children are elements of $W$. + \item\label{both-subtrees-property} for every $v \in W$, either it has + descendants in $W$ in at most one of its subtrees, or both of its + children are elements of $W$. \end{enumerate} We will define the \definedterm{LCA partition with respect to $W$} for a @@ -862,9 +864,9 @@ Each part will be of one of three types: \begin{description} \item[subtree] A \definedterm{subtree of $v$} is $v$ along with all its descendants; it is rooted in $v$. - \item[subtree with hole] A \definedterm{subtree of $v$ with hole $w$} is the subtree of $v$ - minus the subtree of $w$ (for $w$ a descendant of $v$); it is rooted in - $v$. + \item[subtree with hole] A \definedterm{subtree of $v$ with hole $w$} is the + subtree of $v$ minus the subtree of $w$ (for $w$ a descendant of $v$); + it is rooted in $v$. \item[singleton] A singleton vertex $v$, which is the root of such a part. \end{description} |