## Computing the *j*th solution of a first-order query

^{1}
GREYC, Université de Caen, ENSICAEN, CNRS, Campus 2, 14032 Caen Cedex, France; gbagan@info.unicaen.fr; grandjean@info.unicaen.fr

^{2}
Équipe de Logique Mathématique, Université
Denis Diderot, CNRS UMR 7056, 2 place Jussieu, 75251 Paris Cedex 05, France;
durand@logique.jussieu.fr

^{3}
LIF, Université Aix-Marseille 1, CNRS, 39 rue Joliot Curie, 13453 Marseille Cedex 13, France; frederic.olive@lif.univ-mrs.fr

We design algorithms of “optimal" *data complexity* for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems *R ⊂ I x O* whose instances *x ∈ I* may admit of several solutions *R(x) = {y ∈ O : (x,y) ∈ R}*. One associates to such a problem several specific tasks: compute a *random* (for the uniform probability distribution) solution *y ∈ R(x)*; *enumerate* without repetition each solution *y*_{j} in some specific linear order *y _{0} < y_{1} < ... < y_{n-1}* where

*R(x) = {y*; compute the solution

_{0},...,y_{n-1}}*y*

_{j}of

*rank*

*j*in the linear order

*<*. Algorithms of “minimal" data complexity are presented for the following problems: given any first-order formula and any structure

*S*of bounded degree:

*(1)*compute a random element of ;

*(2)*compute the

*j*th element of for some linear order of ;

*(3)*enumerate the elements of in lexicographical order. More precisely, we prove that, for any fixed formula

*φ*, the above problem

*(1)*(resp.

*(2)*,

*(3)*) can be computed within average constant time (resp. within constant time, with constant delay) after a linear

*(O(|S|))*precomputation. Our essential tool for deriving those complexity results is a

*normalization*procedure of first-order formulas on

*bijective structures*.

Mathematics Subject Classification: 68Q15 / 68Q19

Key words: Complexity of enumeration / first-order queries / structures of bounded degree / linear time / constant time / constant delay

*© EDP Sciences, 2007*