m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex13
1 files changed, 7 insertions, 6 deletions
diff --git a/mgr.tex b/mgr.tex
index 5f8e6ab..cb631e0 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -330,16 +330,17 @@ MSO to automata direction in this work. See for example BojaƄczyk's text
Consider a computational problem whose inputs are of the form $(S, q) \in
\mathcal{S} \times \mathcal{Q}$ for some set of \definedterm{structures}
-$\mathcal{S}$ and some set of \definedterm{questions} $\mathcal{Q}$. This
-induces a \definedterm{question answering problem} which is divided into two
-phases:
+$\mathcal{S}$ and some set of \definedterm{questions} $\mathcal{Q}$, and answers
+come from a set $\mathcal{A}$. In other words, fix a function $f : \mathcal{S}
+\times \mathcal{Q} \to \mathcal{A}$. This induces a \definedterm{question
+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 a data structure
- $S'$.
- \item[questions] $S'$ is used to handle questions $q_1, \ldots$ from
- $\mathcal{Q}$.
+ $S'$ (which can be an arbitrary data structure, not necessarily an
+ element of $\mathcal{S}$).
+ \item[questions] Given $S'$ and $q \in \mathcal{Q}$, output $f(S, q)$.
\end{description}
We are interested in the time complexities of both phases. We use the following