RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (234.1 KB) | References |

RAIRO-Theor. Inf. Appl. 42, 147-164 (2008)
DOI: 10.1051/ita:2007046

Computing the jth solution of a first-order query

Guillaume Bagan¹, Arnaud Durand², Etienne Grandjean¹ and Frédéric Olive³

¹ GREYC, Université de Caen, ENSICAEN, CNRS, Campus 2, 14032 Caen Cedex, France; gbagan@info.unicaen.fr; grandjean@info.unicaen.fr
² Équipe de Logique Mathématique, Université Denis Diderot, CNRS UMR 7056, 2 place Jussieu, 75251 Paris Cedex 05, France; durand@logique.jussieu.fr
³ LIF, Université Aix-Marseille 1, CNRS, 39 rue Joliot Curie, 13453 Marseille Cedex 13, France; frederic.olive@lif.univ-mrs.fr

(Published online: 18 January 2008)

Abstract
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\subset I\times O$ whose instances $x\in I$ may admit of several solutions $R(x) = \{y\in O: (x,y) \in R\}$ . One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution $y \in R(x)$ ; enumerate without repetition each solution y_j in some specific linear order $y_0 <y_1 < \ldots <y_{n-1}$ where $R(x)=\{y_0,\dots,y_{n-1}\}$ ; compute the solution 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 $\varphi(\bar{v})$ and any structure S of bounded degree: (1) compute a random element of $\varphi(S)=\{\bar{a}: (S,\bar{a})\models\varphi(\bar{v})\}$ ; (2) compute the jth element of $\varphi(S)$ for some linear order of $\varphi(S)$ ; (3) enumerate the elements of $\varphi(S)$ in lexicographical order. More precisely, we prove that, for any fixed formula $\varphi$ , 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