From 27c1d117c45622c462f11b648cab1c1d185263f4 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 16 Dec 2021 17:04:19 +0100 Subject: Small improvement in introduction --- mgr.tex | 10 +++++----- 1 file 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} -- cgit v1.2.3