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