m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/mgr.tex
diff options
context:
space:
mode:
Diffstat (limited to 'mgr.tex')
-rw-r--r--mgr.tex15
1 files changed, 8 insertions, 7 deletions
diff --git a/mgr.tex b/mgr.tex
index 4db589a..f842b9b 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -965,9 +965,9 @@ It's easy to see that $W'''$ is still LCA closed. It is obvious that it is
necessary to add at least all the vertices added in step
\ref{partition-ready-last-step}, otherwise property \ref{both-subtrees-property}
of partition readiness won't be satisfied. What we will show is that no other
-new vertices need to be added. Take $v \in W''$ that had descendants from $W''$
+new vertices need to be added. Take $v \in W''$ that has descendants from $W''$
in both its subtrees, let $v_l$ and $v_r$ be its left and right child,
-respectively. Without loss of generality, suppose $v_l$ was not an element of
+respectively. Without loss of generality, suppose $v_l$ is not an element of
$W''$. The only reason we would need to add even more vertices after adding
$v_l$ would be if $v_l$ had descendants in both its children's subtrees in
$W'''$. First let's show that it has descendants in $W''$ in at most one of its
@@ -1116,9 +1116,9 @@ components:
}\label{subtree-with-hole-figure}
\end{figure}
-$w$ is not a part of the subtree with hole, but we will need to consider it
-during the following computation, so for ease of notation we will define $u_0 :=
-w$, extending the path of $u_i$'s.
+The node $w$ is not a part of the subtree with hole, but we will need to
+consider it during the following computation, so for ease of notation we will
+define $u_0 := w$, extending the path of $u_i$'s.
Figure \ref{subtree-with-hole-figure} depicts a subtree with hole labeled
according to this nomenclature.
@@ -1210,7 +1210,8 @@ Since $T$'s root is the root of one of the parts of our LCA partition, in the
end we will know whether or not $A$ accepts $T$ after relabeling. Handling each
part takes $O_A(1)$ 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_A(m \log m)$.
+their LCA closure, thus question answering takes time $O_A(m \log m)$. This
+concludes the proof of Theorem \ref{relabel-regular-queries-theorem}.
\section{The full algorithm}
@@ -1280,7 +1281,7 @@ exponentially.
With our algorithm we get, ``for free'', an
\qptime{$O_{\varphi}(n)$}{$O_{\varphi}(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}.
+structures are MSO interpretable in trees in linear time \cite{courcelle1992}.
\printbibliography