m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-16 17:04:19 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-16 17:04:19 +0100
commit27c1d117c45622c462f11b648cab1c1d185263f4 (patch)
tree6426f7fc87cc59aa4298eb926a51d7a11f5c984d
parent4285da4999acaa2bca23148e91e1f184dc72415d (diff)
Small improvement in introduction
-rw-r--r--mgr.tex10
1 files changed, 5 insertions, 5 deletions
diff --git a/mgr.tex b/mgr.tex
index 1e1eeb9..0066062 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -98,11 +98,11 @@ single tree and formula, varying the valuations we ask about, and thus allow a
preprocessing step over the formula and tree. In this case, the above naive
algorithm could be improved with Amarilli et al.'s \cite{amarilli2019} data
structure that allows updates of the underlying tree. Let $m$ be the size of a
-given question, i.e. $|W_1 \cup ... \cup W_k|$. Amarilli's result allows us to
-preprocess the tree in linear time, label it with a choice of $W_1, \ldots, W_k$
-in time $O(m \log n)$, then answer model checking in constant time, thus greatly
-improving over the naive algorithm for questions that talk about a small number
-of vertices compared to the size of the whole tree.
+given question, i.e. $m = |W_1 \cup \ldots \cup W_k|$. Amarilli's result allows
+us to preprocess the tree in linear time, label it with a choice of $W_1,
+\ldots, W_k$ in time $O(m \log n)$, then answer model checking in constant time,
+thus greatly improving over the naive algorithm for questions that talk about a
+small number of vertices compared to the size of the whole tree.
\section{Main result}