A. Amarilli, P. Bourhis, L. Jachiet, and S. Mengel, A circuit-based approach to efficient enumeration, 44th International Colloquium on Automata, Languages, and Programming, vol.111, p.15, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01639179

R. Andrade, M. Wannagat, C. C. Klein, V. Acuña, A. Marchettispaccamela et al., Enumeration of minimal stoichiometric precursor sets in metabolic networks, Algorithms for Molecular Biology, vol.11, issue.1, p.25, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01368653

D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, vol.65, issue.1, pp.21-46, 1996.

G. Bagan, Mso queries on tree decomposable structures are computable with linear delay, International Workshop on Computer Science Logic, pp.167-181, 2006.

D. Barth, O. David, F. Quessette, V. Reinhard, Y. Strozecki et al., Efficient generation of stable planar cages for chemistry, International Symposium on Experimental Algorithms, pp.235-246, 2015.

K. Böhmová, L. Häfliger, M. Mihalák, T. Pröger, G. Sacomoto et al., Computing and listing st-paths in public transportation networks, Theory of Computing Systems, vol.62, issue.3, pp.600-621, 2018.

B. Courcelle, Linear delay enumeration and monadic second-order logic, Discrete Applied Mathematics, vol.157, issue.12, pp.2675-2700, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00333846

N. Creignou and J. Hébrard, On generating all solutions of generalized satisfiability problems, vol.31, pp.499-511, 1997.

A. Durand and Y. Strozecki, Enumeration complexity of logical query problems with second-order variables, LIPIcs-Leibniz International Proceedings in Informatics, vol.12, 2011.

C. Costa-florêncio, J. Daenen, and J. Ramon, Van den Bussche, and Dries Van Dyck. Naive infinite enumeration of context-free languages in incremental polynomial time, J. UCS, vol.21, issue.7, pp.891-911, 2015.

J. Flum and M. Grohe, Parameterized complexity theory, 2006.

E. Fredkin, Trie memory, Communications of the ACM, vol.3, issue.9, pp.490-499, 1960.

. Donald-e-knuth, Combinatorial algorithms, part 1, volume 4a of the art of computer programming, 2011.

D. E. Knuth, The art of computer programming, vol.3, 1997.

M. Luby and B. Veli?kovi´veli?kovi´c, On deterministic approximation of dnf, Algorithmica, vol.16, issue.4-5, pp.415-433, 1996.

A. Mary, ´ Enumération des Dominants Minimaux d'un graphe, 2013.

A. Mary and Y. Strozecki, Efficient enumeration of solutions produced by closure operations, 33rd Symposium on Theoretical Aspects of Computer Science, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01388505

K. Murakami and T. Uno, Efficient algorithms for dualizing large-scale hypergraphs, Discrete Applied Mathematics, vol.170, pp.83-94, 2014.

G. Pruesse and F. Ruskey, Generating linear extensions fast, SIAM Journal on Computing, vol.23, issue.2, pp.373-386, 1994.

R. C. Read, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, vol.5, issue.3, pp.237-252, 1975.

N. Schweikardt, L. Segoufin, and A. Vigny, Enumeration for fo queries over nowhere dense graphs, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, SIGMOD/PODS '18, pp.151-163, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01895786

L. Segoufin, Enumerating with constant delay the answers to a query, Proceedings of the 16th International Conference on Database Theory, pp.10-20, 2013.
DOI : 10.1145/2448496.2448498
URL : https://hal.archives-ouvertes.fr/hal-00907085

Y. Strozecki, Enumeration complexity and matroid decomposition, 2010.

Y. Strozecki, On enumerating monomials and other combinatorial structures by polynomial interpolation. Theory of Computing Systems, vol.53, pp.532-568, 2013.
DOI : 10.1007/s00224-012-9442-z
URL : http://www.prism.uvsq.fr/%7Eystr/poly_longue.pdf

T. Uno, Constant time enumeration by amortization, Workshop on Algorithms and Data Structures, pp.593-605, 2015.
DOI : 10.1007/978-3-319-21840-3_49

R. Wright, B. Richmond, A. Odlyzko, and B. D. Mckay, Constant time generation of free trees, SIAM Journal on Computing, vol.15, issue.2, pp.540-548, 1986.
DOI : 10.1137/0215039
URL : http://cs.anu.edu.au/people/bdm/papers/ConstantTimeTrees.pdf

, A Proof of Proposition 1

, We use a Gray code to do this in constant time. More precisely, we represent a model of C in n registers R 1 ,. .. , R n where R i holds the value of x i in this model. We initialize the registers such that R i = 1 if x i ? C and R i = 0 otherwise, The models of C on variables X are exactly the assignments of the form 1 C ? ? for any ? : X \ var(C) ? {0, 1}

.. .. Now-let-k-=-|x-\-var(c)|-and-?-:-{1 and .. , We start by storing the values of ? in an array of size k. We then execute Output(1, n) which outputs the first model of C. After that, we run a Gray code enumeration on the subsets of a set of size k. For each new element generated, the Gray code algorithm flips a bit at some position i. We thus switch the bit of R ?(i) and call Output(1, n), n} be such that X \ var(C) = {x ?(1)