On the synchronizing probability function and the triple rendezvous time as approaches to Cerny's conjecture
François Gonze, Raphaël M. Jungers · Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) · 2014
We push further a recently proposed method for studying synchronizing automata and Cerný’s conjecture, namely, the synchronizing probability function. In this method, the synchronizing phenomenon is reinterpreted as a Two-Player game, in which the optimal strategies of the players can be obtained through a Linear Program. Our analysis will mainly focus on the concept of the triple rendezvous time, the shortest length of a word mapping three states onto a single one. It represents an intermediate step in the synchronizing process, and is a good characterization of its overall length. Our contribution is twofold. First, using the synchronizing probability function and properties of linear programming, we provide a new upper bound on the triple rendezvous time. Second, we disprove a conjecture on the synchronizing probability function by exhibiting a family of counterexamples. We discuss the game theoretic approach and possible further work in the light of our results. 1 Synchronizing automata and Cerný’s conjecture An automaton is called synchronizing if there exists a sequence of letters which maps all the states onto a single one (see next subsection for rigorous definitions). Figure 1 shows an example of such an automaton. Figure 1: A synchronizing automaton on four states with two letters, a and b. The sequence of letters abbbabbba leads to state 1, whatever the initial state is. ∗ICTEAM Institute, UCLouvain, Louvain La Neuve, Belgium. This work was also supported by the communaute francaise de Belgique Actions de Recherche Concertees and by the Belgian Program on Interuniversity Attraction Poles initiated by the Belgian Federal Science Policy Office. †ICTEAM Institute, UCLouvain, Louvain La Neuve, Belgium. R. Jungers is a F.R.S.-FNRS Research Associate Synchronizing automata have been the source of intense and exciting research in the past 50 years. The interest for the subject appeared in computers and relay control systems in the 60s. The aim was to restore the control over these devices without knowing their current state (see [13], [10]). In the 80s and 90s, the use of synchronizing automata spread through applications in robotics and industry. More recently, synchronizing automata have found biological applications. The survey [19] gives a more detailed overview of synchronizing automata applications. In this paper, we represent automata with matrices. In this representation, a set of states S ⊂ Q of an automaton (with n possible states) is represented by its characteristic vector, i.e. a 1× n vector x ⊂ {0, 1}n for which xi = 1 if state i ∈ S, and 0 otherwise. A state is represented by such a binary vector with a single entry equal to one. The letters of the automaton will be represented as n × n matrices, such that applying the letter a represented by matrix A to an automaton with characteristic vector x is equivalent to computing the product xA. More precisely: A (deterministic, finite state, complete) automaton (DFA) is a set of m column-stochastic matrices Σ ⊂ {0, 1}n×n (where m,n are respectively the number of letters in the alphabet, and the number of states of the automaton). That is, the matrices in Σ have binary entries, and they satisfy AeT = e, where e is the 1× n all-ones vector. We write Σt for the set of matrices which are products of length t of matrices taken in Σ. We refer to these matrices as words of length t. Definition 1. An automaton Σ ⊂ {0, 1}n×n is synchronizing if there is a finite product A = Ac1 . . . AcW : Aci ∈ Σ and an index 0 < i ≤ n which satisfy A = ei e, where ei is the ith standard basis vector (1× n). In this case, the sequence of letters c1 . . . cW is said to be a synchronizing word. Jan Cerný stated his conjecture on DFA in 1964 [6] [7]. Although it is very simple in its formulation, it has not been proven since then. The conjecture is the following: Conjecture 1. Cerný’s conjecture, 1964 [7] Let Σ ⊂ {0, 1}n×n be a synchronizing automaton. Then, there is a synchronizing word of length at most (n− 1)2. In [6], Cerný proposes an infinite family of automata attaining this bound, for any number of states. The automaton represented in Figure 1 is the representative of this family on four states. Indeed, its smallest synchronizing word is abbbabbba, which is composed of nine letters. The examples of synchronizing automata attaining this bound, or even getting close to it for a large number of states, are very infrequent (some families of such automata are developed in [1]). Since its formulation, Conjecture 1 has been the subject of intense research. Up to now, the best upper bound on the length of a minimal synchronizing word for an automaton of size n is even not quadratic, but is equal to (n3 − n)/6 [14] [15]. This bound in the general case has been holding for more than 30 years. Conjecture 1 has been proven to hold for subfamilies of automata [2,3,5,6,8,9,12,18]. Very recently, several attempts to introduce a probabilistic point of view to this problem have appeared in the literature (see [17] for a recent presentation of the main ideas). A state of the art overview is presented in [19]. Our work is based on the synchronizing probability function, introduced in 2011 [11]. This tool allows to reformulate the synchronizing property in terms of game theory. It is promising in that it offers a connection with an a priori unrelated concept, which relies on a strong theoretical basis (see [4], [16]). In the next section, we will introduce the concept of triple rendezvous time, and obtain an upper bound on this value, based on the synchronizing probability function. In Section 3, we will describe a particular family of automata which, amongst other interesting properties, refutes a recent conjecture on the synchronizing probability function. We will not redefine here the concept of synchronizing probability function, which can be found in [11], nor give the full proofs of the results, which will appear in later publications. 2 Upper bound on the triple rendezvous time In what follows, the weight of a vector is the number of its non-zero elements. As defined in [11], A(t) is the bloc-row matrix containing all the matrix representations of words of length at most t of the automaton considered. Definition 2. Let us consider a synchronizing automaton ∑ . We define the triple rendezvous time T3, ∑ as the smallest integer such that A(T3,∑) contains a column of weight superior or equal to 3. In other words, it is equal to the length of the smallest word for which one of the states has a pre-image of cardinality three. In the following, we will use T3 for T3, ∑ when there is no ambiguity on the automaton. Although the concept of triple rendezvous time is a very natural concept, we are not aware of any attempt to bound its value for synchronizing automata. We will obtain an upper bound on the triple rendezvous time by using the synchronizing probability function. See [11] for a more detailed overview of this function. Our motivation for studying T3 is that there are empirical evidences that its value is correlated with the length of a shorter synchronizing word. Indeed, for the known automata achieving the bound of Conjecture (1), T3 is around n, and the SPF is growing close to linearly. These considerations led to the following conjecture, which states that, although the SPF can deviate from a linear growth, at time equal to multiples of (n + 1), it has to catch up with the slope corresponding to Conjecture 1: Conjecture 2. in [11] (Conjecture 2) For any synchronizing automaton A and for any j ≥ 1, j ≤ n− 1, k(1 + (j − 1)(n + 1)) ≥ j/(n− 1). This conjecture would imply Cerný’s conjecture [11]. It also would imply that the triple rendezvous time for an automaton on n nodes is lower or equal to n + 2 ( see [11], section 4). We will see later that it is not the case. We now present an upper bound on T3 (see GandALF 2014 proceedings for the proofs). First, it is not difficult to see that in a synchronizing automaton ∑ with n states, T3, ∑ ≤ n(n−1) 2 + 1. Indeed, there are n(n−1) 2 possible pairs of states, and therefore as A(t) grows and has to evolve at each step, we obtain our result. However, it is possible to improve this bound: Theorem 1. In a synchronizing automaton with n states, T3 ≤ (n)(n+4) 4 − Parity n 4 , with Parity n = 0 if n is even, and 1 if n is odd. Proof. (sketch) We have the following lemma: Lemma 1. if t < T3, then k(t) can only take the values 2/(n+ s), 0 ≤ s ≤ n− 1, and this value cannot be optimal at more than b(n− s)/2c+ 1 steps. This allows us to derive a better bound on T3 by counting all the possible steps before T3: