From 438ab64ce75ab47cfa26674a3d01241ed8f4f663 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 5 Feb 2022 21:33:38 +0100 Subject: Reword question answering definition --- mgr.tex | 13 +++++++------ 1 file 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 -- cgit v1.2.3