This paper situates itself in the theory of variable length codes and of finite automata where the concepts of completeness and synchronization play a central role. In this theoretical setting, we investigate the problem of finding upper bounds to the minimal length of synchronizing and incompletable words of a finite language X in terms of the length of the words of X. This problem is related to two well-known conjectures formulated by Cˇerny´ and Restivo respectively. In particular, if Restivo's conjecture is true, our main result provides a quadratic bound for the minimal length of a synchronizing pair of any finite synchronizing complete code with respect to the maximal length of its words.
The concepts of completeness and synchronization play a central role in Computer Science since they appear in the study of several problems on variable length codes and on finite automata. According to a well-known result of Schu¨tzenberger, the property of completeness provides an algebraic characterization of finite maximal codes, which are the objects used in Information Theory to construct optimal sequential codings. Let X be a set of words on an alphabet A. The set X is complete if any word on the alphabet A is a factor of some word belonging to X∗, otherwise it is incomplete. In the latter case, any word which is factor of no word of X∗ is said to be incompletable in X. In [18], Restivo conjectured that a finite incomplete set X has always an incompletable word whose length is quadratically bounded by the maximal length of the words of X. Results on this problem have been obtained in [5, 14, 15, 18].
The property of synchronization plays a natural role in Information Theory where it is relevant for the construction of decoders that are able to efficiently cope with decoding errors caused by noise during the data transmission. A set
X is synchronizing if there are two words u, v of X∗ such that whenever ruvs ∈ X∗, r, s ∈ A∗, one has also ru, vs ∈ X∗. The pair of words (u, v) is called synchronizing pair of X.
In the study of synchronizing sets, the search for synchronizing words of
minimal length in a prefix complete code is tightly related to that of synchronizing
words of minimal length for synchronizing complete deterministic automata and
the celebrated Cˇ erny´ Conjecture [12] (see also [
In this paper we are interested in finding upper bounds to the minimal lengths of incompletable and synchronizing words of a finite set X in terms of the size of X. We recall that the size of X is the parameter `(X) defined as the maximal length of the words of X.
Let L be a class of finite languages. For all n, d > 0, we denote by RL(n, d) the least positive integer r satisfying the following condition: any incomplete set X ∈ L on a d-letter alphabet such that `(X) ≤ n has an incompletable word of length r. Similarly, we denote by CL(n, d) the least positive integer c satisfying the following condition: any synchronizing set X ∈ L on a d-letter alphabet such that `(X) ≤ n has a synchronizing pair (u, v) such that |uv| ≤ c.
In this context, the main result of this paper provides a bridge between the parameters RL(n, d) and CL(n, d). More precisely, denoting by F and by M the classes of finite languages and of complete finite codes respectively, we show that, for all n, d > 0,
CM(n, d) ≤ 2RF (n, d + 1) + 2n − 2.
In particular, if Restivo’s conjecture is true, the latter bound gives
CM(n, d) = O(n2), thus providing a quadratic bound in the size of the set for the minimal length of a synchronizing pair of a finite synchronizing complete code.
In the second part of the paper, we study the dependence of the parameters RL(n, d) and CL(n, d) upon the number of letters d of the considered alphabet, by showing that both the parameters have a low rate of growth. More precisely, we show that, for the class L of finite languages (resp. codes, prefix codes), we have
RL(n, d) ≤
RL(dlog2 den, 2) , blog2 dc and, for the class L of finite complete languages (resp. codes, prefix codes), we have 2
Preliminaries In this section we shortly recall some basic results of the theory of automata and of the theory of codes which will be useful in the sequel and we fix the corresponding notation used in the paper. The reader can refer to [4, 13] for more details.
Let A be a finite alphabet and let A∗ be the free monoid of words over the alphabet A. The identity of A∗ is called the empty word and is denoted by . The length of a word w ∈ A∗ is the integer |w| inductively defined by | | = 0, |wa| = |w| + 1, w ∈ A∗, a ∈ A. Given w ∈ A∗ and a ∈ A, we denote by |w|a the number of occurrences of the letter a in w. For any finite set W of words we denote by `(W ) the maximal length of the words of W . The number `(W ) will be called the size of W . Given words u, w ∈ A∗, u is said to be a factor of w if w = αuβ, for some α, β ∈ A∗. The set of all factors of w is denoted by Fact(w). Given a set W of words, the set of the factors of all the words of W is denoted by Fact(W ). Similarly, given a word w, a word u is said to be a prefix of w if w = uβ, for some β ∈ A∗. A set X is said to be prefix if, for any u, v ∈ X, with v = uw, with w ∈ A∗, one has w = .
Definition 1. Let X be a subset of A∗. A pair of words (r, s) is an X-completion of a word w if rws ∈ X∗. A word having an X-completion is a completable word of X; conversely, a word with no X-completion is an incompletable word of X. The set X is complete if all words of A∗ are completable words of X; X is incomplete, otherwise.
Another crucial notion of this paper is that of synchronizing set. Definition 2. A pair (u, v) ∈ X∗ × X∗ is a synchronizing pair of X if for every X-completion (r, s) of uv, it holds that
ru, vs ∈ X∗ .
The set X is synchronizing if it has a synchronizing pair.
The notion of synchronizing pair of a set is strictly related to that of constant. A word c of X∗ is said to be a constant of X if, for every u1, u2, u3, u4 ∈ A∗ such that u1cu2, u3cu4 ∈ X∗, one has u1cu4, u3cu2 ∈ X∗. The following result holds. Lemma 1. Let X be a subset of A∗. If (u, v) is a synchronizing pair of X, uv is a constant of X. Conversely, if c is a constant of X, (c, c) is a synchronizing pair of X. 2.1
The notions of complete and synchronizing sets provide a rich structure in the case that the set is a code. It is worth to shortly describe some fundamental results on such sets. A set X of words over an alphabet A is said to be a (variable length) code over A if it fulfills the unique factorization property, that is, for every word u ∈ X∗, there exists a unique sequence x1, . . . , xk of words of X such that u = x1 · · · xk. A well-known example of codes is given by prefix sets. The notion of code is strictly related to the one of monomorphism. Let A and B be two alphabets. A map h : A∗ → B∗ is said to be a monomorphism or (sequential) encoding if h is injective and, for every u, v ∈ A∗, one has h(uv) = h(u)h(v). The following lemma shows a well-known link between the notion of code and that of monomorphism.
Proposition 1. Let h : A∗ → B∗ be a monomorphism. Then the set X = h(A) is a code over B. If X is a code over B and X has the same cardinality of A, then every bijection between A and X can be extended to a (unique) monomorphism h : A∗ → B∗.
In view of Proposition 1, the monomorphism defined by a prefix code will be called prefix encoding. A submonoid of A∗ is said to be free if it is generated by a code. An important result due to Schu¨tzenberger provides a characterization of a free submonoid of A∗ in terms of a property called stability. A submonoid N of A∗ is said to be stable if, for every word u ∈ A∗, the existence of words n1, n2, n3, n4 of N such that n2 = un1 and n4 = n3u implies u ∈ N . Theorem 1. Let N be a submonoid of A∗. Then N is a free submonoid of A∗ if and only if N is stable.
Let us finally recall some well-known results on codes.
Theorem 2. (Kraft-McMillan inequality) Let A be a d-letter alphabet with d ≥ 2 and let k1, . . . , kn be a finite sequence of positive integers such that n X d−ki ≤ 1 .
i=1 Then k1, . . . , kn is the sequence of the code-word lengths of a prefix code over A. Given a code X over an alphabet A, X is said to be maximal if it is not properly contained in any other code over A. Let us recall another important result due to Schu¨tzenberger. It provides a tight relation between maximal and complete codes.
Theorem 3. Let A be a d-letter alphabet and let X be a regular code of A∗. The following conditions are equivalent: – X is a maximal code; – X is a complete code; – Px∈X d−|x| = 1.
Given a set X over an alphabet A, X is said to be maximal prefix if it is prefix and it is not properly contained in any other prefix code over A. In the case of prefix codes we get:
Theorem 4. Let X be a prefix code of A∗ and suppose that X is a regular language. The following conditions are equivalent: – X is maximal prefix; – X is right complete, that is, for every word u ∈ A∗, uA∗ ∩ XA∗ 6= ∅; – X is a maximal code.
It is worth recalling that Theorems 3 and 4 hold in the more general case of thin codes that is, for all the subsets X of A∗ such that X ∩ A∗wA∗ = ∅, for some word w ∈ A∗. Another relevant result concerning synchronizing and complete codes is the following.
Theorem 5. Let X be a synchronizing and complete code. Then there exists a constant c ∈ X∗ such that cA∗c ⊆ X∗. Conversely, if X is a code such that there exists a word c ∈ X∗ with cA∗c ⊆ X∗, then X is synchronizing and complete.
Synchronizing automata and the Cˇ erny´ conjecture A finite non-deterministic automaton is a tuple A = hQ, A, δ, I, F i where Q is a finite set of elements called states, δ is a map
δ : Q × A −→ P(Q), where P(Q) is the power set of Q, and I, F are subsets of Q. The map δ is called the transition function of A while I is called the set of the initial states and F is the set of the final states. The canonical extension of the map δ to the set Q × A∗ is still denoted by δ. If P is a subset of Q and u is a word of A∗, we denote by δ(P, u) and δ(P, u−1) the sets: δ(P, u) = {δ(s, u) | s ∈ P },
δ(P, u−1) = {s ∈ Q | δ(s, u) ∈ P }.
If no ambiguity arises, the sets δ(P, u) and δ(P, u−1) are denoted P u and P u−1, respectively. With the automaton A, we can associate a directed labelled multigraph G = (Q, E), where the set E of edges is defined as E = {(p, a, q) ∈ Q × A × Q | q ∈ δ(p, a)}. We recall that if p, q ∈ Q, then q ∈ pu with u ∈ A∗, is u equivalent to the existence of a path c = p −→ q in G labelled by u. The label of c is denoted by ||c||. A word u ∈ A∗ is said to be accepted by A if Iu∩F 6= ∅. The language accepted by A, denoted by LA, is the set of all the words accepted by A. An automaton A is said to be unambiguous if the following condition holds: for every q1, q2, q3, q4 ∈ Q and for every u, v ∈ A∗ one has q2, q3 ∈ q1u,
q4 ∈ q2v ∩ q3v =⇒ q2 = q3.
An automaton A is said to be deterministic if for every q ∈ Q and for every a ∈ A, Card(qa) ≤ 1.
An automaton A is said to be complete if for every u ∈ A∗, there exists some q ∈ Q such that Card(qu) ≥ 1.
An automaton A is said to be transitive if for every p, q ∈ Q, there exists u ∈ A∗ such that q ∈ pu. In the sequel, we will only consider automata A such that I = F = {1}, that is, with a unique initial and final state denoted 1. In particular, the tuple of the automaton A will be simply denoted A = hQ, A, δ, 1i. Moreover, in the sequel, we will only consider transitive automata.
An unambiguous automaton A is said to be synchronizing if there exist two words w1, w2 ∈ A∗ such that Qw1 ∩ Qw−1 = { } 2 1 .
As is well known, a deterministic automaton A is synchronizing if and only if there is a word u such that Card(Qu) = 1. Such a word is said to be a synchronizing word of A. The following celebrated conjecture has been raised in [12]. Cˇ erny´ Conjecture. Each synchronizing and complete deterministic automaton with n states has a synchronizing word of length (n − 1)2.
Let us recall an important problem related to the Cˇ erny´ Conjecture. Let G be a finite, directed multigraph with all its vertices of the same outdegree. Then G is said to be aperiodic if the greatest common divisor of the lengths of all cycles of the graph is 1. The graph G is called a Road coloring graph (RC-graph for short) if it is aperiodic and strongly connected. A synchronizing coloring of G is a labeling of the edges of G that transforms it into a complete, deterministic and synchronizing automaton. The Road coloring problem asks for the existence of a synchronizing coloring for every RC-graph. In 2007, Trahtman proved the following remarkable result [19].
Theorem 6. Every RC-graph has a synchronizing coloring.
Let us conclude this section by recalling some well-known properties of the automaton that accepts the submonoid generated by a finite set (see, e.g., [6]). Let X be a finite set of words over an alphabet A. By using a standard construction, one can associate with X a transitive automaton denoted by AX = hQ, A, δ, 1i that accepts X∗.
Lemma 2. Let X be a regular code (resp., prefix set). Then AX is an unambiguous (resp., deterministic) automaton. Conversely, let A be an automaton such that LA = X∗ where X ∩ X2X∗ = ∅. If A is unambiguous (resp., deterministic), then X is a code (resp. a prefix set).
Incompletable words of a regular set are characterized by the following. Lemma 3. Let X be a regular set and A = hQ, A, δ, 1i be a transitive automaton accepting X∗. Then w ∈ A∗ is a completable word of X if and only if Qw 6= ∅.
In particular, X is complete if and only if A is complete.
Similarly it is possible to characterize synchronizing pairs of regular codes [6]. Lemma 4. Let X be a regular code and A = hQ, A, δ, 1i be a transitive unambiguous automaton accepting X∗ and w1, w2 ∈ A∗. Then (w1, w2) is a synchronizing pair of X if and only if w1w2 ∈ X∗ and Qw1 ∩ Qw2−1 = { } 1 .
Consequently, X is synchronizing if and only if A is synchronizing. 3
The main result The main result of this paper is related to a problem that was formulated in [18] by Restivo. Let L be a class of finite languages. For all n > 0 we set RL(n) = sup RL(n, d) , d≥1
CL(n) = sup CL(n, d) .
d≥1 In [18], it was conjectured that if F is the class of all finite languages, then RF (n) ≤ 2n2. If we restrict ourselves to prefix codes, we get Proposition 2. ([18]) Let P be the class of finite prefix codes. Then
RP (n) ≤ 2n2.
However, in the general case, the previous bound was disproved in [14]. A more general and larger counterexample is given in [15]. We can thus state a slightly weaker version of the problem as follows.
Conjecture 1. (Restivo’s Conjecture) Let F be the class of all finite languages. Then RF (n) = O(n2).
In this context, the main result of this paper is the following.
Proposition 3. Let M be the class of complete finite codes. For all n, d > 0,
CM(n, d) ≤ 2RF (n, d + 1) + 2n − 2.
Before proving Proposition 3, it is convenient to discuss some interesting consequences of this result. First, if Restivo’s conjecture is true, we get
CM(n, d) = O(n2).
Moreover, the bound above would be sharp, as we explain below. Consider the
prefix code Xn = aAn−1 ∪ bAn−2 on the alphabet A = {a, b}. The minimal
automaton accepting Xn∗ has been studied in [
CM(n, 2) ≥ CP (n, 2) ≥ (n − 1)2, for the parameter CM(n, 2).
It is also worth to do a remark on a recent result by B´eal and Perrin. In [
Let us now proceed to prove Proposition 3. For this purpose, let X be a finite complete synchronizing code over a d-letter alphabet A and let n = `(X). Let AX = hQ, A, δ, 1i be the unambiguous automaton that accepts X∗. The proof of Proposition 3 is based upon the following lemma.
Lemma 5. Let (v1, v2) be a synchronizing pair of X. Then, there exist words w1, w2 ∈ A∗ such that |w1|, |w2| ≤ RF (n, d + 1),
Qw1 ⊆ Qv1,
Qw2−1 ⊆ Qv2−1.
Indeed, assume that Lemma 5 holds. As X is complete, the word w1w2 has an Xcompletion (r, s). With no loss of generality, we may suppose that |r|, |s| ≤ n − 1. Since (v1, v2) is a synchronizing pair, one has
Q(rw1) ∩ Q(w2s)−1 ⊆ Qw1 ∩ Qw2−1 ⊆ Qv1 ∩ Qv2−1 = {1}.
Moreover, the word rw1w2s ∈ X∗ is accepted by AX and therefore there is a state q ∈ Q such that q ∈ 1rw1 and 1 ∈ qw2s. Thus, q ∈ Q(rw1) ∩ Q(w2s)−1 ⊆ {1}, that is, q = 1. This proves that rw1, w2s ∈ X∗ and by Lemma 4 (rw1, w2s) is a synchronizing pair of X.
Now, our main goal is to prove Lemma 5. For the sake of simplicity, we will prove the existence of the word w1 that fulfills the conditions of Lemma 5 since the proof of the existence of the word w2 can be obtained by using a symmetric construction. The main tool of this proof is a new automaton we construct below.
Let (v1, v2) be a synchronizing pair of X. If v1 = , the statement is trivially verified by w1 = v1. Thus we assume v1 6= and set v1 = ua, with u ∈ A∗ and a ∈ A.
Let a0 be a symbol not belonging to A and let A0 = A ∪ {a0}. We consider a new automaton A0 = hQ, A0, δ0, 1i where the transition map δ0 is defined as follows: for every q ∈ Q and a ∈ A, δ0(q, a) = δ(q, a) and δ0(q, a0) = (δ(q, a) ∪ {1} if q ∈/ δ(Q, u),
δ(q, a) \ {1} if q ∈ δ(Q, u).
It is useful to remark that, by construction, the automaton A0 is still transitive. Let Y be the minimal generating set of the language accepted by A0. Thus, LA0 = Y ∗ and Y ∩ Y 2Y ∗ = ∅.
Lemma 6. The set Y is incomplete.
Proof. By (1) one has δ0(Q, ua0) = δ(Q, ua)\{1} = δ(Q, v1)\{1} and δ0(Q, v2−1) = δ(Q, v2). Taking into account that (v1, v2) is a synchronizing pair of X, one derives
δ0(Q, ua0) ∩ δ0(Q, v2−1) = (δ(Q, v1) ∩ δ0(Q, v2−1)) \ {1} = ∅ .
It follows that δ0(Q, ua0v2) = ∅. This equation proves that the automaton A is not complete. Thus, by Lemma 3, Y is an incomplete set. (1) tu
Lemma 7. It holds that `(Y ) ≤ `(X).
Proof. In order to prove the statement, it is enough to show that, for every y ∈ Y, there exists x ∈ X with |y| ≤ |x|.
Let y = a1 · · · ak ∈ Y , with ai ∈ A0, for i = 1, . . . , k. Since Y ∩ Y 2Y ∗ = ∅, in the graph of A0 there is a path c0 = 1 −a→1 q1 −a→2 q2 −→ · · · a−k→−1 qk −a→k 1, a3 where, for every i = 1, . . . , k, qi 6= 1. Let us now construct a path c in the graph of AX such that ||c|| = x ∈ X, with |x| ≥ |y|, so completing the proof. b By the definition of A0, any edge p −→ q of the graph of A0 with b 6= a0 is a0 also an edge of the graph of A. Moreover, if p −→ q is an edge of the graph of A0 a with q 6= 1, then p −→ q is an edge of the graph of A. Thus, by replacing in c0, every transition qi −→ qi+1, by qi −→ qi+1 and deleting the last edge qk −a→k 1, a0 a we find a path
d = 1 −b→1 q1 −b→2 q2 · · · b−k→−1 qk of the graph of A. Since A is transitive, one can catenate d with a simple path from qk to 1. In such a way, we obtain a path c of the graph of A starting and ending in 1, with all intermediate states distinct from 1 and length ≥ k + 1. As is well known, as A is unambiguous, the label x of such a path is a word of the minimal generating set X of X∗. Since |x| ≥ k + 1 = |y|, this completes the proof. tu
We now prove the following lemma.
Lemma 8. Let v be an incompletable word of Y of minimal length. There exists a word w1 ∈ A∗ such that |w1| ≤ |v|,
Proof. Let v be an incompletable word of Y of minimal length, with the number |v|a0 as small as possible. Then, by Lemma 3, one has δ0(Q, v) = ∅.
The letter a0 necessarily occurs in v, since by the completeness of A, one has δ0(Q, r) = δ(Q, r) 6= ∅ for all r ∈ A∗. Thus, we can write v = u1a0u2, with u1 ∈ A∗ and u2 ∈ A0∗.
Let us verify that δ(Q, u1) ⊆ δ(Q, u). Indeed, suppose the contrary. Then, by (1), one has
δ0(Q, u1a0) = δ(Q, u1a) ∪ {1} = δ0(Q, u1a) ∪ {1} and consequently, δ0(Q, u1au2) ⊆ δ0(Q, u1a0u2) = ∅. Thus, u1au2 is an incompletable word of Y , but this contradicts the minimality of |v|a0 .
We conclude that δ(Q, u1) ⊆ δ(Q, u) and therefore taking w1 = u1a and recalling that v1 = ua, one has δ(Q, w1) ⊆ δ(Q, v1) and |w1| ≤ |v|. The statement follows. tu
Let us finally remark that Lemma 7 and Lemma 8 yield |w1| ≤ RF (n, d + 1),
Let us check that u is incompletable. By contradiction, deny. Then r0us0 ∈ X∗, for some r0, s0 ∈ A∗. Consequently, h(r0us0) = h(r0)vsh(s0) ∈ h(X∗), thus implying that v is completable in h(X). Now (2) easily follows from the latter, (4) and (5).
The aim of this section is to study how much the parameters RL(n, d) and CL(n, d) vary according to the cardinal number d of the alphabet. We start to analyze the parameter RL(n, d). In the sequel, B denotes the binary alphabet B = {a, b}. The following lemmas are needed for the proof of Proposition 4. Lemma 9. Let Y ⊆ A∗ be a complete finite set. Then any word w of A∗ has a Y -completion (y, s) with y ∈ Y ∗.
Lemma 10. Let h : A∗ → B∗ be a prefix encoding and Y ⊆ A∗. The set h(Y ) is complete if and only if Y and h(A) are complete.
Encoding a d-letter alphabet on a suitable complete binary prefix code one obtains Proposition 4. Let L be the class of finite languages (resp. codes). Then RL(n, d) ≤
RL(dlog2 den, 2) .
blog2 dc Proof. Let A be a d-letter alphabet and let X be a finite incompletable language over A of size n. By Theorems 2 and 3, there exists a maximal prefix code Y over B such that Card(Y ) = d and, for every y ∈ Y , blog2 dc ≤ |y| ≤ dlog2 de. Let h : A∗ → B∗ be a monomorphism constructed by Y . In particular, for every a ∈ A, we have
blog2 dc ≤ |h(a)| ≤ dlog2 de.
By (3) the size of h(X) is not greater than ndlog2 de. By Lemma 10, since X is incompletable, h(X) is incompletable as well. Let v be an incompletable word in h(X) of minimal length. Hence we have
Since h(A) is a complete prefix code, by Theorem 4, there exist u ∈ A∗ and s ∈ B∗ such that h(u) = vs and by (3) |v| ≤ RL(dlog2 den, 2).
|u| ≤
|v| blog2 dc
. (2) (3) (4) (5) tu
Let us now analyze the parameter CL(n, d). The next two lemmas are useful for this purpose. In particular the following lemma is algebraically similar to Lemma 10.
Lemma 11. Let h : A∗ → B∗ be a monomorphism and let Y ⊆ A∗ be a complete set. The set h(Y ) is synchronizing if and only if Y and h(A) are synchronizing. Lemma 12. Let k1, . . . , kn, d > 0 be such that gcd(k1, k2, . . . , kn) = 1 , n X d−ki = 1. i=1 Then k1, . . . , kn are the code-word lengths of a synchronizing complete prefix code over d letters.
Remark 1. It is worth noticing that a finite synchronizing complete prefix code over d letters satisfies both the conditions of Lemma 12. Indeed, by Theorem 3, if X = {x1, . . . , xn} is a complete code over d letters, one gets Pn i=1 d−ki = 1.
Moreover, by Theorem 5, there exists a constant x ∈ X∗ for X such that xA∗x ⊆ X∗. Let γ = gcd(k1, k2, . . . , kn). Since, by the latter result, x2, xax ∈ X∗, with a ∈ A, γ should divide both 2|x| and 2|x| + 1, whence γ = 1.
As an application of the two lemmas above, encoding a d-letter alphabet on a suitable complete binary synchronizing code, one obtains the following result: Proposition 5. Let L be the class of finite complete languages (resp. codes, prefix codes). Then Proposition 6. Let L be the class of finite languages (resp. codes, prefix codes). Then 3. M.-P. B´eal, M. V. Berlinkov, D. Perrin, A quadratic upper bound on the size of a synchronizing word in one-cluster automata, Int. J. Found. Comput. Sci., 22, 277–288, 2011. 4. J. Berstel, D. Perrin, Ch. Reutenauer, Codes and Automata, Encyclopedia of Mathematics and its Applications, 129, Cambridge University Press, 2009. 5. J. M. Bo¨e, A. de Luca, A. Restivo, Minimal complete sets of words, Theoret.
Comput. Sci., 12, 325–332, 1980. 6. A. Carpi, On synchronizing unambiguous automata, Theoret. Comput. Sci., 60, 285–296, 1988. 7. A. Carpi, F. D’Alessandro, The Synchronization Problem for Strongly Transitive Automata, in: M. Ito, M. Toyama eds., DLT 2008 Developments in Language Theory, Lecture Notes in Computer Science, Vol. 5257, pp. 240–251, Springer, Berlin, 2008. 8. A. Carpi, F. D’Alessandro, Strongly transitive automata and the Cˇerny´ conjecture
Acta Informatica, 46, 591–607, 2009. 9. A. Carpi, F. D’Alessandro, The synchronization problem for locally strongly transitive automata, in: R. Kra´loviˇc, D. Niwin´ski eds., MFCS 2009 Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci., Vol. 5734, pp. 211–222, Springer, Berlin, 2009. 10. A. Carpi, F. D’Alessandro, On the Hybrid Cˇerny´-Road coloring problem and Hamiltonian paths, in: Y. Gao, H. Lu, S. Seki, S. Yu eds., DLT 2010 Developments in Language Theory, Lecture Notes in Comput. Sci., Vol. 6224, pp. 124–135, Springer, Berlin, 2010. 11. A. Carpi, F. D’Alessandro, Independent sets of words and the synchronization problem, Advances in Applied Mathematics, 50, 339–355, 2013. 12. J. Cˇerny´, Pozna´mka k. homog´ennym experimenton s koneˇcny´mi automatmi, Mat.
fyz. cas SAV, 14, 208–215, 1964. 13. A. de Luca, F. D’Alessandro, Teoria degli Automi Finiti, 68, Springer Italia, 2013. 14. G. Fici, E. V. Pribavkina, J. Sakarovitch, On the Minimal Uncompletable Word
Problem, CoRR, arXiv: 1002.1928, 2010. 15. V. V. Gusev, E. V. Pribavkina, On Non-complete Sets and Restivo’s Conjecture, in: G. Mauri, A. Leporati eds., DLT 2011 Developments in Language Theory, Lecture Notes in Comput. Sci., Vol. 6795, pp. 239–250, Springer, Berlin, 2011. 16. J. E. Pin, Le probl`eme de la synchronization et la conjecture de Cerny, Th`ese de 3`eme cycle, Universit´e de Paris 6, 1978. 17. J. E. Pin, Sur un cas particulier de la conjecture de Cerny, in: G. Ausiello, C.
Bo¨hm eds., 5th ICALP Lecture Notes in Computer Science, Vol. 62, pp. 345–352, Springer, Berlin, 1978. 18. A. Restivo, Some remarks on complete subsets of a free monoid, in: A. de Luca ed., Non-Commutative Structures in Algebra and Geometric Combinatorics, International Colloquium, Arco Felice, July 1978, Quaderni de “La Ricerca Scientifica”, CNR, 109, 19–25, 1981. 19. A. N. Trahtman, The road coloring problem, Israel J. Math., 172, 51–60, 2009. 20. M. V. Volkov, Synchronizing automata and the Cerny conjecture, in: C. Mart´ınVide, F. Otto, H. Fernau eds., LATA 2008 Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., Vol. 5196, pp. 11–27, Springer, Berlin, 2008.