Computing the jth solution of a first-order query

Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne; Olive, Frédéric

doi:10.1051/ita:2007046

Bagan, Guillaume ; Durand, Arnaud ; Grandjean, Etienne ; Olive, Frédéric ¹

¹ LIF, Université Aix-Marseille 1, CNRS, 39 rue Joliot Curie, 13453 Marseille Cedex 13, France;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 147-164

Voir la notice de l'article provenant de la source Numdam

Résumé

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} < ... < 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 $ϕ (\bar{v})$ and any structure $S$ of bounded degree: $(1)$ compute a random element of $ϕ (S) = {\bar{a} : (S, \bar{a}) ⊧ ϕ (\bar{v})}$ ; $(2)$ compute the $j$ th element of $ϕ (S)$ for some linear order of $ϕ (S)$ ; $(3)$ enumerate the elements of $ϕ (S)$ 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.

MR Zbl

DOI : 10.1051/ita:2007046

Classification : 68Q15, 68Q19
Keywords: complexity of enumeration, first-order queries, structures of bounded degree, linear time, constant time, constant delay

Affiliations des auteurs :

Bagan, Guillaume ; Durand, Arnaud ; Grandjean, Etienne ; Olive, Frédéric ¹

¹ LIF, Université Aix-Marseille 1, CNRS, 39 rue Joliot Curie, 13453 Marseille Cedex 13, France;

@article{ITA_2008__42_1_147_0,
     author = {Bagan, Guillaume and Durand, Arnaud and Grandjean, Etienne and Olive, Fr\'ed\'eric},
     title = {Computing the jth solution of a first-order query},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {147--164},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {1},
     year = {2008},
     doi = {10.1051/ita:2007046},
     mrnumber = {2382549},
     zbl = {1149.68028},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2007046/}
}

TY  - JOUR
AU  - Bagan, Guillaume
AU  - Durand, Arnaud
AU  - Grandjean, Etienne
AU  - Olive, Frédéric
TI  - Computing the jth solution of a first-order query
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 147
EP  - 164
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2007046/
DO  - 10.1051/ita:2007046
LA  - en
ID  - ITA_2008__42_1_147_0
ER  -

%0 Journal Article
%A Bagan, Guillaume
%A Durand, Arnaud
%A Grandjean, Etienne
%A Olive, Frédéric
%T Computing the jth solution of a first-order query
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 147-164
%V 42
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2007046/
%R 10.1051/ita:2007046
%G en
%F ITA_2008__42_1_147_0

Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne; Olive, Frédéric. Computing the jth solution of a first-order query. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 147-164. doi: 10.1051/ita:2007046

Cité par Sources :

Parcourir par

Geodesic

Parcourir par