diff options
| -rw-r--r-- | mgr.tex | 15 |
1 files changed, 8 insertions, 7 deletions
@@ -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 |