R. Et-qui-atteignent-toutes-les-u-sources-de, En remarquant qu'il y a k(n ? r) transitions et qu'elles sont toutes différentiables

T. Si, ensemble des applications de T dans G ne contient que l'application vide Cette application appartientàappartientà ? que si et seulement si U = ? donc ?(0, 0, g) = 1 et ?

. Si, U est vide alors toute fonction de T vers G appartientàappartientà ? et donc ?

U. Supposons-que-s-n-'appartienne-pasàpasà, Alors dans ce cas il s'agit de choisir les images desélémentsdeséléments de T \ {e} parmi l'ensemble G de telle façon que tous lesélémentsleséléments de U aient un antécédent

M. Almeida, N. Moreira, and R. Reis, EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA, International Journal of Foundations of Computer Science, vol.19, issue.04, pp.751-765, 2008.
DOI : 10.1142/S0129054108005930

J. Berstel, L. Boasson, O. Carton, I. David, C. Bassino et al., On the average complexity of moore's state minimization algorithm Average case analysis of moore's state minimization algorithm Asymptotic enumeration of minimal automata (Cité Citéà la page 6.) [BN07] Frédérique Bassino and Cyril Nicaud. Enumeration and random generation of accessible automata, STACSCités aux pages 6, 27 et 46.) [BDN12] Frédérique Bassino, Julien David, and Cyril Nicaud STACSCitéCitéà la page 6.) [Brz62] J. A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events Mathematical theory of Automata MRI Symposia Series. (Cités aux pages 6, pp.123-134509, 1962.

P. Caron, J. Champarnaud, and L. Mignot, Small Extended Expressions for Acyclic Automata, Lecture Notes in Computer Science, vol.63, issue.1,2, pp.198-207, 2009.
DOI : 10.1016/0304-3975(96)00028-X

P. Caron, J. Champarnaud, and L. Mignot, Acyclic automata and small expressions using multi-tilde-bar operators, Theoretical Computer Science, vol.411, issue.38-39
DOI : 10.1016/j.tcs.2010.05.023
URL : http://doi.org/10.1016/j.tcs.2010.05.023

. Comput and . Sci, Random generation of deterministic acyclic automata using markov chains, CitéCitéà la page 49.) [CF11] Vincent Carnino and Sven De Felice CIAACités aux pages 7 et 51.) [CF12] Vincent Carnino and Sven De Felice. Sampling different kinds of acyclic automata using markov chainsCités aux pages 7 et 51.) [CN12], pp.38-393423, 2010.

A. Carayol and C. Nicaud, Distribution of the number of accessible states in a random deterministic automaton, STACS, pp.194-205, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00678213

[. Champarnaud and T. Paranthoën, Random generation of DFAs, Theoretical Computer Science, vol.330, issue.2, pp.221-235, 2005.
DOI : 10.1016/j.tcs.2004.03.072

J. David, The average complexity of moore's state minimization algorithm is o(n log log n), MFCS, pp.318-329, 2010.

J. David, Average complexity of Moore???s and Hopcroft???s algorithms, Theoretical Computer Science, vol.417
DOI : 10.1016/j.tcs.2011.10.011

P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer, Random generation of combinatorial structures: Boltzmann samplers and beyond, Proceedings of the 2011 Winter Simulation Conference (WSC), pp.577-625, 2004.
DOI : 10.1109/WSC.2011.6147745
URL : https://hal.archives-ouvertes.fr/hal-00654267

[. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, DCFS, pp.67-78, 2001.

[. Domaratzki, Improved bounds on the number of automata accepting finite languages, Developments in Language TheoryCitéCité`Citéà la, pp.209-219, 2002.

A. [. Erdös and . Rényi, On random graphs, I, pp.290-297, 1959.

P. Erdos and P. Turán, On some problems of a statistical group-theory. III, Acta Mathematica Academiae Scientiarum Hungaricae, vol.18, issue.3-4, pp.3-4309, 1967.
DOI : 10.1007/BF02280290

W. Feller, An Introduction to Probability Theory and Its Applications, 1968.

S. De, F. , and C. Nicaud, Brzozowski algorithm is generically super-polynomial for deterministic automata, Developments in Language Theory, pp.179-190, 2013.

S. De, F. , and C. Nicaud, Random generation of deterministic acyclic automata using the recursive method, CSR, pp.88-99, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00841835

P. Flajolet and A. M. Odlyzko, Random Mapping Statistics, Lecture Notes in Computer Science, vol.434, pp.329-354, 1989.
DOI : 10.1007/3-540-46885-4_34
URL : https://hal.archives-ouvertes.fr/inria-00075445

P. Flajolet and R. Sedgewick, Analytic Combinatorics, pp.40-42, 2009.
DOI : 10.1017/CBO9780511801655
URL : https://hal.archives-ouvertes.fr/inria-00072739

[. Flajolet, P. Zimmermann, and B. Van-cutsem, A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, vol.132, issue.1-2
DOI : 10.1016/0304-3975(94)90226-7
URL : https://hal.archives-ouvertes.fr/hal-00917729

I. Good, An Asymptotic Formula for the Differences of the Powers at Zero, The Annals of Mathematical Statistics, vol.32, issue.1, pp.249-256, 1961.
DOI : 10.1214/aoms/1177705156

J. E. Hopcroft, AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON, The Theory of Machines and Computations, pp.189-196, 1971.
DOI : 10.1016/B978-0-12-417750-5.50022-1

E. John, J. D. Hopcroft, and . Ullman, Introduction to Automata Theory, Languages and Computation, 1979.

E. Donald and . Knuth, The Art of Computer Programming, Volume I : Fundamental Algorithms, 1973.

E. Donald and . Knuth, The Art of Computer Programming, Volume III : Sorting and Searching, 1973.

E. Donald and . Knuth, The Art of Computer Programming, Volume II : Seminumerical Algorithms, 1981.

A. Korshunov, Enumeration of finite automata, Problemy Kibernetiki, vol.34, pp.5-82, 1978.

A. Valery and . Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Applied Mathematics, vol.154, issue.3, pp.537-551, 2006.

D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times, 2006.
DOI : 10.1090/mbk/058

G. Melançon, I. Dutour, and M. Bousquet-mélou, Random Generation of Directed Acyclic Graphs, Electronic Notes in Discrete Mathematics, vol.10, pp.202-207, 2001.
DOI : 10.1016/S1571-0653(04)00394-4

F. Edward and . Moore, Gedanken-experiments on sequential machines, Automata Studies, pp.129-153, 1956.

C. Nicaud, Average State Complexity of Operations on Unary Automata, MFCS, pp.231-240, 1999.
DOI : 10.1007/3-540-48340-3_21
URL : https://hal.archives-ouvertes.fr/hal-00620109

H. [. Nijenhuis and . Wilf, Combinatorial algorithms. Computer science and applied mathematics, pp.14-75, 1975.

J. Gary, P. , and D. B. Wilson, Exact sampling with coupled markov chains and applications to statistical mechanics, Random Struct. Algorithms, vol.9, issue.12, pp.223-252, 1996.

D. Revuz, Minimisation of acyclic deterministic automata in linear time, Theoretical Computer Science, vol.92, issue.1, pp.181-189, 1992.
DOI : 10.1016/0304-3975(92)90142-3
URL : https://hal.archives-ouvertes.fr/hal-00619678

J. Rémy, Un procédé itératif de dénombrement d'arbres binaires et son applicationàapplicationà leur génération aléatoire, Theoretical Informatics and Applications -Informatique Théorique et Applications, pp.179-195, 1985.

[. Tabakov and M. Y. Vardi, Experimental Evaluation of Classical Automata Constructions, Proceedings of the 12th international conference on Logic for Programming, Artificial Intelligence, and Reasoning , LPAR'05, pp.396-411, 2005.
DOI : 10.1007/11591191_28