Recherche



Thèmes de recherche

Caractérisations logiques des classes de complexité - Complexité de l'énumération.

Publications

G. Grandjean, F. Olive. "Descriptive complexity for pictures languages", [pdf]

N. Creignou, F. Olive, J. Schmidt. "Enumerating all solutions of a Boolean CSP by non-decreasing weight", SAT 2011. [pdf]

G. Bagan, A. Durand, E. Grandjean, F. Olive. "Computing the jth solution of a first-order query", in Z. Ezik editors, RAIRO 2007. [pdf]

A. Durand, F. Olive. "First-order queries over one unary function", in Z. Ezik editors, Computer Science Logic, selected paper of CSL'06, Szeged (Hungary), LNCS 4207 (2006), pp.334-348. Springer-Verlag. [pdf]

A. Durand, E. Grandjean, F. Olive. "New results on arity vs number of variables", Rapport technique du LIF , Université de Provence 2004. [pdf]

E. Grandjean, F. Olive. "Graph properties checkable in linear time in the number of vertices", Journal of Computer and System Sciences, vol. 68 (2004) pp. 546-597. [pdf]

B. Courcelle, F. Olive. "Une axiomatisation au premier ordre des arrangements de pseudodroites euclidiennes", Annales de l'Institut Fourier, T. 9 (1999) fascicule 3, pp. 883-903. [pdf]

F. Olive. "A conjunctive logical characterization of non-deterministic linear time", in M. Nielsen and W. Thomas editors, Computer Science Logic, selected paper of CSL'97, Aahrus (Denmark) , LNCS 1414 (1998), pp. 360-372. Springer-Verlag. [ps]

E. Grandjean, F. Olive. "Monadic logical definability of nondeterministic linear time", Journal of Computational Complexity, vol. 7 (1998) pp. 54-97. [ps]

M. More, F. Olive. "Rudimentary langages and second-order logic", Mathematical Logic Quaterly, vol. 43 (1997) pp. 419-426. [pdf]

F. Olive, "Caractérisations logiques des problèmes NP-complets : robustesse et normalisation", Thèse de doctorat, Université de Caen, July 1996. [ps.gz]

E. Grandjean, F. Olive. "Monadic logical definability of NP-complete problems", in J. Tyurin and L. Pacholski editors, Computer Science Logic, selected paper of CSL'94, Kazimierz (Poland), LNCS 933 (1995), pp.190-204. Springer-Verlag. [ps] <<