Publications

A. Durand, J. Ebbing, J. Kontinen, H. Vollmer. Dependence logic with a majority quantifier Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), pages 252-263, Leibniz International Proceedings in Informatics (LIPIcs) [arxiv version]
A. Durand, Y. Strozecki. Enumeration Complexity of Logical Query Problems with Second-order Variables Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL, pp 189-202, Leibniz International Proceedings in Informatics (LIPIcs) [pdf]
A. Durand, J. Kontinen. Hierarchies in Dependence Logic ACM Transactions on Computational Logic (to appear) [arxiv version]
A. Durand, N. Jones, J. Makowsky, M. More. Fifty Years of the Spectrum Problem: Survey and New Results To appear in the Bulletin of Symbolic Logic [pdf]
A. Durand, M. Hermann, G. Nordh. Trichotomy in the complexity of minimal inference Theory of Computing Systems, 50(3), pages 446-491. Journal version of the LICS'09 paper [pdf]
A. Durand, M. Habib. Complexity Issues for the Homogeneous Set Sandwich Problem Discrete Applied Mathematics, 159(7), pages 574-580, 2011
G. Bagan, A. Durand, E. Filiot, O. Gauwin. Efficient Enumeration for Conjunctive Queries over X-underbar Structures Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL'10), Lecture Notes in Computer Science, ARCoSS, vol. 6247, pages 80-94. 2010 [pdf]
A. Durand, M. Hermann, G. Nordh. Trichotomy in the complexity of minimal inference 24th Annual IEEE Symposium on Logic in Computer Science (LICS'2009), pp. 387-396, 2009 [pdf]
G. Bagan, A. Durand, E. Grandjean, F. Olive. Computing the jth solution of a first-order query. RAIRO Theor. Inf. Appl. vol. 42, pp. 147-164, 2008
A. Durand, M. Hermann. On the Counting Complexity of Propositional Circumscription. Information Processing Letters, 106(4), p. 164-170, 2008 [pdf]
A. Durand, C. Lautemann, M. More. Counting results in weak formalisms. ACM Sigact News , Complexity Theory Column 57 This paper is dedicated to the memory of Clemens Lautemann. This is a new and shorter version of the 1997 unpublished paper ``Counting results in weak formalisms'' (see below)
G. Bagan, A. Durand, E.Grandjean. On Acyclic Conjunctive Queries and Constant Delay Enumeration. Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, LNCS 4646, pages 208-222, 2007 [pdf] [longer version]
A. Durand, E.Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Transactions on Computational Logic, vol (8)4, 2007. [pdf]
A. Durand, F. Olive. First-order queries over one unary function. Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, LNCS 4207, pages 334-348. Springer, 2006 [pdf]
E. Ailloud, A. Durand. The expressive power of bijections over weakly arithmetized. Theory of Computing Systems, 39(2):297-309, 2006. [pdf]
A. Durand, E. Grandjean. The complexity of acyclic conjunctive queries revisited. Technical report, 2005. The version available for download is that of arXiv:cs/0605008v1 (May, 2006). [pdf]
A. Durand, M. Hermann, P.G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science, 340(3):496-513, 2005. [pdf]
A. Durand, E. Grandjean, F. Olive. New results on arity vs. number of variables. Research report 20-2004, LIF, Marseille, France, April 2004. [pdf]
A. Durand. Habilitation ŕ diriger des recherches. Université Paris 12, 2003. [pdf]
A. Durand, M. Hermann. The inference problem for propositional circumscription of affine formulas is coNP-complete. In H. Alt and M. Habib, editors, 20th Symposium on Theoretical Aspects of Computer Science (STACS'03), LNCS 2607, pages 451-462. Springer, 2003. [pdf]
A. Durand. Binary-NP and the power of one first-order universal quantifier. Information and Computation, 178(1):12-22, 2002. [pdf]
A. Durand, M. Hermann, L. Juban. On the complexity of recognizing the hilbert bases of a linear diophantine system. Theoretical Computer Science, 270(1-2):625-642, 2002. [pdf]
A. Durand, M. More. Non erasing, counting and majority over the linear hierarchy. Information and Computation, 174(2):132-142, 2002. [pdf]
D. Beauquier, T. Crolard, A. Durand, A. Slissenko. Impossibility of essential real-time garbage collection in the general case. In CSIT'01, pages 17-20, Yerevan (Armenia), 2001.
A. Durand, M. Hermann, P.G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. In M. Nielsen and B. Rovan, editors, 25th International Symposium on Mathematical Foundations of Computer Science (MFCS'00), LNCS 1893, pages 323-332. Springer, 2000.
A. Durand, M. Hermann, L. Juban. On the complexity of recognizing the hilbert bases of a linear diophantine system. In L. Pacholski and M. Kutylowski, editors, 24th International Symposium on Mathematical Foundations of Computer Science (MFCS'99), LNCS 1672, pages 92-102. Springer, 1999.
A. Durand. Modeling cache coherence protocol - a case study with flash. In Workshop on Abstract State Machines, pages 111-126. T.U. Magdeburg, 1998.
A. Durand. R. Fagin, B. Loescher. Spectra with only unary function symbols. In M. Nielsen and W. Thomas, editors, Computer Science Logic, selected paper of CSL'97, LNCS 1414, pages 189-202. Springer, 1998. Also available as BRICS notes series NS-97-1 and IBM Research Report RJ 10105. [pdf]
A. Durand, C. Lautemann, M. More. Counting results in weak formalisms. Technical report, S.D.A.D. Université de Caen, 1998. [pdf]
A. Durand, C. Lautemann, T. Schwentick. Subclasses of binary NP. Journal of Logic and Computation, 8(2):189-207, 1998. [pdf]
A. Durand. Hiérarchies de définissabilité logique au second ordre. Thèse de Doctorat. Université de Caen., 1996. [pdf]
A. Durand, S. Ranaivoson. First-order spectra with one binary predicate. Theoretical Computer Science, 160(1-2):305-320, 1996.
A. Durand, S. Ranaivoson. First-order spectra with one binary predicate. In J. Tyurin, L. Pacholski, editors, Computer Science Logic, selected paper of CSL'94, LNCS 933, pages 177-189. Springer, 1995.