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