Let D(n,r) be a random r-out regular directed multigraph on the set of vertices 1,...,n . In this work, we establish that for every r � 2, there existsr > 0 such that diam(D(n,r)) = (1 + �r + o(1))log r n. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on D(n,r). In particular, we determine the asymptotic behaviour ofmax andmin, the maximum and the minimum values of the stationary distribution. We show that with
Several other properties of random DFAs have been studied, both in learning theory and in other contexts, using the @math model. For example, first Korshunov's group, and later Nicaud's group, have studied the probability that random DFA exhibit particular structures, mainly motivated by the analysis of sample and reject algorithms for enumeration of subclasses of automata (see @cite_0 and references therein). Motivated by worst-case hardness results for learning a DFA, Angluin and co-authors have used properties of random DFAs to study the problem of learning a generic DFA @cite_2 @cite_4 . The average-case complexity of DFA minimization algorithms has also received some attention recently @cite_21 @cite_8 . Finally, a series of results have led to a solution of the long-standing C ern 'y conjecture about synchronization of finite automata in the case of random DFA @cite_5 @cite_6 @cite_17 .
@cite_4 @cite_8 @cite_21 @cite_6 @cite_0 @cite_2 @cite_5 @cite_17
2106435631 35268004 2088285637 2295392808 2217322393 94998075 142090792 1522735212
We show that random DNF formulas, random log-depth decision trees and random deterministic finite acceptors cannot be weakly learned with a polynomial number of statistical queries with respect to an arbitrary distribution on examples. We study the number of states of the minimal automaton of the mirror of a rational language recognized by a random deterministic automaton with n states. We prove that, for any d > 0, the probability that this number of states is greater than n d tends to 1 as n tends to infinity. As a consequence, the generic and average complexities of Brzozowski minimization algorithm are super-polynomial for the uniform distribution on deterministic automata. We prove that the average complexity of Moore’s state minimization algorithm is @math , where n is the number of states of the input and k the size of the alphabet. This result holds for a whole family of probabilistic models on automata, including the uniform distribution over deterministic and accessible automata, as well as uniform distributions over classical subclasses, such as complete automata, acyclic automata, automata where each state is final with probability γ∈(0,1), and many other variations. A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerny conjectured in 1964 that if a n-state deterministic automaton has a synchronizing word, then it has a synchronizing word of size at most (n-1)^2. Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization by proving that with high probability, an automaton has a synchronizing word. In this article, we prove that with high probability an automaton admits a synchronizing word of length smaller than n^(1+ ), and therefore that the Cerny conjecture holds with high probability. In this article, we consider deterministic automata under the paradigm of average case analysis of algorithms. We present the main results obtained in the literature using this point of view, from the very beginning with Korshunov’s theorem about the asymptotic number of accessible automata to the most recent advances, such as the average running time of Moore’s state minimization algorithm or the estimation of the probability that an automaton is minimal. While focusing on results, we also try to give an idea of the main tools used in this field. We consider the problem of learning a finite automaton M of n states with input alphabet X and output alphabet Y when a teacher has helpfully or randomly labeled the states of M using labels from a set L. The learner has access to label queries; a label query with input string w returns both the output and the label of the state reached by w. Because different automata may have the same output behavior, we consider the case in which the teacher may "unfold" M to an output equivalent machine M′ and label the states of M′ for the learner. We give lower and upper bounds on the number of label queries to learn the output behavior of M in these different scenarios. We also briefly consider the case of randomly labeled automata with randomly chosen transition functions. We prove that a random automaton with @math states and any fixed non-singleton alphabet is synchronizing with high probability. Moreover, we also prove that the convergence speed is exactly @math as conjectured by Cameron CamConj for the most interesting 2-letter alphabet case. Conjecture that any synchronizing automaton with n states has a reset word of length (n - 1)(2) was made by. Cerny in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. In this paper we study a random automaton that is sampled uniformly at random from the set of all automata with n states and m(n) letters. We show that for m(n) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n(beta), beta > 1 2 we also show that any random automaton with high probability satisfies the. Cerny conjecture.