m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/mgr.tex
diff options
context:
space:
mode:
Diffstat (limited to 'mgr.tex')
-rw-r--r--mgr.tex6
1 files changed, 6 insertions, 0 deletions
diff --git a/mgr.tex b/mgr.tex
index c066fe6..16c4e7a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -326,6 +326,12 @@ automaton, there is a corresponding MSO formula), however we will use only the
MSO to automata direction in this work. See for example BojaƄczyk's text
\cite{bojanczyktoolbox} for a proof of both directions.
+\subsection{Computational Model}
+
+We use the Random Access Machine (RAM) model with uniform cost measure. In
+particular, basic arithmetic operations are assigned a constant cost, regardless
+of bitlength of arguments.
+
\section{Question answering problems}\label{query-answering-problems}
Consider a computational problem whose inputs are of the form $(S, q) \in