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