Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: First-order queries on structures of bounded degree are computable with
  constant delay   A bounded degree structure is either a relational structure all of whose
relations are of bounded degree or a functional structure involving bijective
functions only. In this paper, we revisit the complexity of the evaluation
problem of not necessarily Boolean first-order queries over structures of
bounded degree. Query evaluation is considered here as a dynamical process. We
prove that any query on bounded degree structures is $\constantdelaylin$, i.e.,
can be computed by an algorithm that has two separate parts: it has a
precomputation step of linear time in the size of the structure and then, it
outputs all tuples one by one with a constant (i.e. depending on the size of
the formula only) delay between each. Seen as a global process, this implies
that queries on bounded structures can be evaluated in total time
$O(f(|\phi|).(|\calS|+|\phi(\calS)|))$ and space $O(f(|\phi|).|\calS|)$ where
$\calS$ is the structure, $\phi$ is the formula, $\phi(\calS)$ is the result of
the query and $f$ is some function.
  Among other things, our results generalize a result of \cite{Seese-96} on the
data complexity of the model-checking problem for bounded degree structures.
Besides, the originality of our approach compared to that \cite{Seese-96} and
comparable results is that it does not rely on the Hanf's model-theoretic
technic (see \cite{Hanf-65}) and is completely effective.

15
The categories of this paper are: nucl-ex
11
The categories of this paper are: hep-lat
8
The categories of this paper are: hep-ex
34
The categories of this paper are: chem-ph
5
The categories of this paper are: gr-qc
13
The categories of this paper are: quant-ph
27
The categories of this paper are: comp-gas
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
16
The categories of this paper are: stat
19
The categories of this paper are: eess
3
The categories of this paper are: physics
6
The categories of this paper are: astro-ph