From 840dfd0f4eee7fd1f7f9b0035de72b9ec2d29a89 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 5 Nov 2021 11:59:19 +0100 Subject: Reword and change font --- mgr.tex | 12 ++++++------ 1 file 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 -- cgit v1.2.3