From fe426a9b9c217f7854597eb3e55e15a97d756f19 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 2 Jul 2022 18:43:48 +0200
Subject: Fix typos and style problems

---
 mgr.tex | 15 ++++++++-------
 1 file 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
 
-- 
cgit v1.2.3