m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex12
1 files changed, 6 insertions, 6 deletions
diff --git a/mgr.tex b/mgr.tex
index 215540a..d3aa05c 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -307,16 +307,16 @@ MSO to automata direction in this work.
\section{Query answering problems}\label{query-answering-problems}
Consider a computational problem whose inputs are of the form $(S, q) \in
-\mathcal{S} \times Q$ for some set of \definedterm{structures} $\mathcal{S}$ and
-some set of \definedterm{queries} $Q$. This induces a \definedterm{query
-answering problem} which is divided into two phases:
+\mathcal{S} \times \mathcal{Q}$ for some set of \definedterm{structures}
+$\mathcal{S}$ and some set of \definedterm{queries} $\mathcal{Q}$. This induces
+a \definedterm{query answering problem} which is divided into two phases:
\begin{description}
\item[preprocessing] An input structure $S \in \mathcal{S}$ is given and a
- \definedterm{preprocessing algorithm} outputs an indexing structure
+ \definedterm{preprocessing algorithm} outputs a data structure
$S'$.
- \item[queries] On-line queries $q_1, \ldots$ from $Q$ about $S$ need to be
- handled, with access to the preprocessing output $S'$.
+ \item[queries] $S'$ is used to handle queries $q_1, \ldots$ from
+ $\mathcal{Q}$.
\end{description}
We are interested in the time complexities of both phases. We use the following