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