m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/mgr.tex
diff options
context:
space:
mode:
Diffstat (limited to 'mgr.tex')
-rw-r--r--mgr.tex16
1 files changed, 9 insertions, 7 deletions
diff --git a/mgr.tex b/mgr.tex
index 00e45a9..217e99d 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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}