Synchronization Problems in Automata without Non-trivial Cycles
Andrew Ryzhikov

	



Synchronization Problems in Automata
 without Non-trivial Cycles
    Andrew Ryzhikov^1, 2
    
	^1Université Grenoble Alpes, Laboratoire G-SCOP, 38031 Grenoble, France

	^2United  Institute of Informatics Problems  of NASB, 
	220012 Minsk, Belarus

	ryzhikov.andrew@gmail.com

==========================================================================================================================================================================================




	We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We investigate the complexity of finding a synchronizing set of states of maximum size. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizing subset of states in such automata are NP-complete.

	
	


§ INTRODUCTION


The concept of synchronization is widely studied in automata theory and has a lot of different applications in such areas as manufacturing, coding theory, biocomputing, semigroup theory and many others <cit.>. Let A = (Q, Σ, δ) be a complete deterministic finite automaton (which we simply call an automaton in this paper), where Q is a set of states, Σ is a finite alphabet and δ: Q ×Σ→ Q is a transition function. Note that our definition of an automaton does not include initial and accepting states. The function δ can be naturally extended to a mapping Q ×Σ^* → Q, which we also denote as δ, in the following way: for x ∈Σ and a ∈Σ^* we recursively set δ(q, xa) = δ(δ(q, x), a). An automaton is called synchronizing if there exists a word that maps all its states to a fixed state. Such word is called a synchronizing word. A state q ∈ Q is called a sink state if all letters from Σ map q to itself.

In this paper synchronization of weakly acyclic automata is studied. A simple cycle in an automaton A = (Q, Σ, δ) is a sequence q_1, …, q_k of its states such that all the states in the sequence are different and there exist letters x_1, …, x_k ∈Σ such that δ(q_i, x_i) = q_i + 1 for 1 ≤ i ≤ k - 1 and δ(q_k, x_k) = q_1. A simple cycle is a self-loop if it consists of only one state. An automaton is called weakly acyclic if all its simple cycles are self-loops. In other words, an automaton is weakly acyclic if and only if there exists an ordering q_1, q_2, …, q_n of its states such that if δ(q_i, x) = q_j for some letter x ∈Σ, then i ≤ j (such ordering is called a topological sort). Since a topological sort can be found in polynomial time <cit.>, this class can be recognized in polynomial time. Weakly acyclic automata are called acyclic in <cit.> and partially ordered in <cit.>, where in particular the class of languages recognized by such automata is characterized.

Weakly acyclic automata arise naturally in synchronizing automata theory. Section <ref> of this paper shows several examples of existing proofs where weakly acyclic automata appear implicitly in complexity reductions. Surprisingly, most of the computational problems that are hard for general automata remain very hard in this class despite its very simple structure. Thus, investigation of weakly acyclic automata provides good lower bounds on the complexity of many problems for general automata.  An automaton is called aperiodic if for any word w ∈Σ^* and any state q ∈ Q there exists k such that δ(q, w^k) = δ(q, w^k + 1), where w^k is a word obtained by k concatenations of w <cit.>. Obviously, weakly acyclic automata form a proper subclass of aperiodic automata, thus all hardness results hold for the class of aperiodic automata.

The concept of synchronization is often used as an abstraction of returning control over an automaton when there is no a priori information about its current state, but the structure of the automaton is known. If the automaton is synchronizing, we can apply a synchronizing word to it, and thus it will transit to a known state. If we want to perform the same operation when the current state is known to belong to some subset of states of the automaton, we come to the definition of a synchronizing set. A set S ⊆ Q of states of an automaton A is called synchronizing if there exists a word w ∈Σ^* and a state q ∈ Q such that the word w maps each state s ∈ S to the state q. The word w is said to synchronize the set S. It follows from the definition that an automaton is synchronizing if and only if the set Q of all its states is synchronizing. Consider the problem Sync Set of deciding whether a given set S of states of an automaton A is synchronizing.


	 Sync Set

	 Input: An automaton A and a subset S of its states;

	 Output: Yes if S is a synchronizing set, No otherwise.


The Sync Set problem is PSPACE-complete <cit.>, even for binary strongly connected automata <cit.> (an automaton is called binary if its alphabet has size two, and strongly connected if any state can be mapped to any other state by some word). In <cit.> it is shown that the Sync Set problem is solvable in polynomial time for orientable automata if the cyclic order respected by the automaton is provided in the input. This problem is also solvable in polynomial time for monotonic automata <cit.>. The problem of deciding whether the whole set of states of an automaton is synchronizing is also solvable in polynomial time <cit.>.

One of the most important questions in synchronizing automata theory is the famous Černý conjecture stating that any n-state synchronizing automaton has a synchronizing word of length at most (n - 1)^2. The conjecture is proved for various special cases, including orientable, Eulerian, aperiodic and other automata (see <cit.> for references), but is still open in general. For more than 30 years, the best upper bound was n^3 - n/6, obtained in <cit.>. Recently, a small improvement on this bound has been reported in <cit.>: the new bound is still cubic in n but improves the coefficient 1/6 at n^3 by 4/46875.

While there is a simple cubic bound on the length of a synchronizing word for the whole automaton, there exist examples of automata where the length of a shortest word synchronizing a subset of states is exponential in the number of states <cit.>. For orientable n-state automata, a tight upper bound of (n - 1)^2 is known <cit.>, and this bound is also asymptotically tight for monotonic automata <cit.>. On the other hand, a trivial upper bound 2^n - n - 1 on the length of a shortest word synchronizing a subset of states in a n-state automaton is known <cit.>. In <cit.> Cardoso considers the length of a shortest word synchronizing a subset of states in a synchronizing automaton.

We assume that the reader is familiar with the notions of an NP-complete problem (refer to the book by Sipser <cit.>), an approximation algorithm and a gap-preserving reduction (for reference, see the book by Vazirani <cit.>). 

Given an automaton A, the rank of a word w with respect to A is the number |{δ(s, w) | s ∈ Q}|, i.e., the size of the image of Q under the mapping defined in A by w. More generally, the rank of a word w with respect to a subset S of states of A is the number |{δ(s, w) | s ∈ S}|. The rank of an automaton (resp. of a subset of states) is the minimum among the ranks of all words w ∈Σ^* with respect to the automaton (resp. to the subset of states).

In this paper we provide various results concerning computational complexity and approximability of the problems related to subset synchronization in weakly acyclic automata. In Section <ref> we prove some lower and upper bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states. In Section <ref> we investigate the computational complexity of finding such words. In Section <ref> we study inapproximability of the problem of finding a subset of states of maximum size. In Section <ref> we give strong inapproximability results for computing the rank of a subset of states in binary weakly acyclic automata. In Section <ref> we show that several other problems related to recognizing a synchronizing set in a weakly acyclic automaton are hard.

A preliminary conference version of this paper was published in <cit.>.



§ BOUNDS ON THE LENGTH OF SHORTEST SYNCHRONIZING WORDS


Each synchronizing weakly acyclic automaton is a 0-automaton (i.e., an automaton with exactly one sink state), which gives an upper bound n(n - 1)/2 on the length of a shortest synchronizing word <cit.>. The same bound can be deduced from the fact that each weakly acyclic automaton is aperiodic <cit.>. However, for weakly acyclic automata a more accurate result can be obtained, showing that weakly acyclic automata of rank r behave in a way similar to monotonic automata of rank r (see <cit.>).


	Let A = (Q, Σ, δ) be a n-state weakly acyclic automaton, such that there exists a word of rank r with respect to A. Then there exists a word of length at most n - r and rank at most r with respect to A.

 Observe that the rank of a weakly acyclic automaton is equal to the number of sink states in it. The conditions of the theorem imply that A has at most r sink states.
	
	 Consider the sets S_1, …, S_t constructed in the following way. Let p_i be the state in S_i - 1 with the smallest index in the topological sort such that p_i is not a sink state. Let x_i, 1 ≤ i ≤ t, be a letter mapping the state p_i to some other state, where S_i = {δ(q, x_i) | q ∈ S_i - 1}, 1 ≤ i ≤ t, and S_0 = Q. Since A has at most r sink states, the word w = x_1 … x_t exists for any t ≤ n - r and has rank at most r with respect to A. 


The following simple example shows that the bound is tight. Consider an automaton A = (Q, Σ, δ) with states q_1, …, q_n. Let each letter except some letter x map each state to itself. For the letter x define the transition function δ(q_i, x) = q_i + 1 for 1 ≤ i ≤ n - r and δ(q_i, x) = q_i for n - r + 1 ≤ i ≤ n. Obviously, A has rank r and shortest words of rank r with respect to A have length n - r.


	Let S be a synchronizing set of states of size k in a weakly acyclic n-state automaton A = (Q, Σ, δ). Then the length of a shortest word synchronizing S is at most k(2n - k - 1)/2.

 Consider a topological sort q_1, …, q_n of the set Q. Let q_s be a state such that all states in S can be mapped to it by a shortest word w = x_1 … x_t. We can assume that the images of all words x_1 … x_j, j ≤ t, are pairwise distinct, otherwise some letter in this word can be removed. Then a letter x_j maps at least one state of the set {δ(q, x_1 … x_j - 1) | q ∈ S } to some other state. Thus the maximum total number of letters in w sending all states in S to q_s is at most (n - k) + (n - k + 1) + … + (n - 1) = k(2n - k - 1)/2, since application of each letter of w increases the sum of the indices of reached states by at least one.  

Consider a binary automaton A = (Q, {0, 1}, δ) with n states q_1, …, q_k - 1, s_1, …, s_ℓ, t, where ℓ = n - k. Define δ(q_i, 0) = q_i, δ(q_i, 1) = q_i + 1 for 1 ≤ i ≤ k - 2,  δ(q_k - 1, 1) = s_1. Define also δ(s_i, 0) = s_i + 1 for 1 ≤ i ≤ℓ - 1, δ(s_i, 1) = t for 1 ≤ i ≤ℓ - 1. Define both transitions for s_ℓ and t as self-loops. Set S = {q_1, …, q_k - 1, s_ℓ}. The shortest word synchronizing S is (10^l - 1)^k-1 of length (k-1)(n - k). The automaton in this example is binary weakly acyclic, and even has rank 2. Figure <ref> gives the idea of the described construction.




As was noted by an anonymous reviewer, for alphabet of size n-2, a better lower bound of (k - 1)(2n - k - 2)/2 can be shown as follows. Let Q = {-1, 0, 1, …, n-2}, Σ = {a_1, …, a_n - 2},


    δ(k, a_i) = {[          k     k > i,;      k - 1     k = i,;         -1 0 < k < i,;          k  k∈{-1, 0} ].


If k < n and S={0, n - 2, n - 3, …, n - k}, then it is easy to see that the shortest word synchronizing S has length (n - k) + (n - k + 1) + … + (n - 2) = (k - 1)(2n - k - 2)/2. For each n and k, this is less than the upper bound of Proposition <ref> by n - 1 only.



§ COMPLEXITY OF FINDING SHORTEST SYNCHRONIZING WORDS


Now we proceed to the computational complexity of some problems, related to finding a shortest synchronizing word for an automaton. Consider first the following problem.


	 Shortest Sync Word

	 Input: A synchronizing automaton A;

	 Output: The length of a shortest synchronizing word for A.


First, we note that the automaton showing inapproximability of Shortest Sync Word in the construction of Berlinkov <cit.> is weakly acyclic.


	For any γ > 0, the Shortest Sync Word problem for n-state weakly acyclic automata with alphabet of size at most n^1 + γ cannot be approximated in polynomial time within a factor of d log n for any d < c_sc unless P = NP, where c_sc is some constant. 


In Berlinkov's reduction to the binary case, the automaton is no longer weakly acyclic. However, the binary automaton showing NP-hardness of Shortest Sync Word in Eppstein's construction <cit.> is weakly acyclic.


	Shortest Sync Word is NP-hard for binary weakly acyclic automata.


Consider now the following more general problem.


	 Shortest Set Sync Word 

	 Input: An automaton A and a synchronizing subset S of its states; 

	 Output: The length of a shortest word synchronizing S.


It follows from Proposition <ref> that the decision version of this problem (asking whether there exists a word of length at most k synchronizing S) is in NP for weakly acyclic automata, so it is reasonable to investigate its approximability.


	The Shortest Set Sync Word problem for n-state binary weakly acyclic automata cannot be approximated in polynomial time within a factor of O(n^1/2 - ϵ) for any ϵ > 0 unless P = NP.


 To prove this theorem, we construct a gap-preserving reduction from the  Shortest Sync Word problem in p-state binary automata, which cannot be approximated in polynomial time within a factor of O(p^1 - ϵ) for any ϵ > 0 unless P = NP <cit.>. Let a binary automaton A = (Q, {0, 1}, δ) be the input of Shortest Sync Word. Let Q = {q_1, …, q_p}. Construct a binary automaton A' = (Q', {0, 1}, δ') with the set of states Q' =  {q_i^(j)| 1 ≤ i ≤ p, 1 ≤ j ≤ p + 1}. Define δ'(q_i^(j), x) = q_k^(j + 1) for 1 ≤ i ≤ p, 1 ≤ j ≤ p, x ∈{0, 1}, where k is such that q_k = δ(q_i, x). Define δ'(q_i^(p + 1), x) = q_i^(p + 1) for 1 ≤ i ≤ p and x ∈{0, 1}. Take S' = {q_i^(1)| 1 ≤ i ≤ p }.
	
Observe that any word synchronizing S' in A' is a synchronizing word for A because of the definition of δ'. In the other direction, we note that a shortest synchronizing word for a p-state automaton in the construction of Gawrychowski and Straszak <cit.> has length at most p. Hence, a shortest synchronizing word for A also synchronizes S' in A'. Thus, the length of a shortest synchronizing word for A is equal to the length of a shortest word synchronizing S' in A', and we get a gap-preserving reduction with gap O(p^1-ϵ) = O(n^1/2 - ϵ), as A' has O(p^2) states. Finally, it is easy to see that A' is binary weakly acyclic.  



§ FINDING A SYNCHRONIZING SET OF MAXIMUM SIZE
 

One possible approach to measure and reduce initial state uncertainty in an automaton is to find a subset of states of maximum size where the uncertainty can be resolved, i.e., to find a synchronizing set of maximum size. This is captured by the following problem.


	 Max Sync Set 

	 Input: An automaton A;

	 Output: A synchronizing set of states of maximum size in A.


Türker and Yenigün <cit.> study a variation of this problem, which is to find a set of states of maximum size that can be mapped by some word to a subset of a given set of states in a given monotonic automaton. They reduce the N-Queens Puzzle problem <cit.> to this problem to prove its NP-hardness. However, their proof is unclear, since the input has size O(log N), and the output size is polynomial in N. Also, the N-Queens Puzzle problem is solvable in polynomial time <cit.>.

First we investigate the PSPACE-completeness of the decision version of the  Max Sync Set problem, which we shall denote as Max Sync Set-D. Its formulation is the following: given an automaton A and a number c, decide whether there is a synchronizing set of states of cardinality at least c in A.


	The Max Sync Set-D problem is PSPACE-complete for binary automata.

 The Sync Set problem is in PSPACE <cit.>. Thus, the Max Sync Set-D problem is also in PSPACE, as we can sequentially check whether each subset of states is synchronizing and compare the size of a maximum synchronizing set to c.
	
	To prove that the Max Sync Set-D problem is PSPACE-hard for binary automata, we shall reduce a PSPACE-complete Sync Set problem for binary automata to it <cit.>. Let an automaton A and a subset S of its states be an input to Sync Set. Let n be the number of states of A. Construct a new automaton A' by initially taking a copy of A. For each state s ∈ S, add n + 1 new states to A' and define all the transitions from these new states to map to s, regardless of the input letter. Define the set S' to be a union of all new states and take c = |S'| = (n + 1)|S|.
	
	Let S_1 be a maximum synchronizing set in A not containing at least one new state q. As S_1 is maximum, it does not contain other n new states that can be mapped to the same state as q. Thus, the size of S_1 is at most n + (n + 1)|S| - (n + 1) < (n + 1)|S| = c. Hence, each synchronizing set of size at least c in A' contains S'. The set S is synchronizing in A if and only if S' is synchronizing in A', as each word w synchronizing S in A corresponds to a word xw synchronizing S' in A', where x is an arbitrary letter. Thus, A' has a synchronizing set of size at least c if and only if S is synchronizing in A. 

Now we proceed to inapproximability results for the Max Sync Set problem in several classes of automata. We shall need some results from graph theory. An independent set I in a graph G is a set of its vertices such that no two vertices in I share an edge. The size of a maximum independent set in G is denoted α(G). The Independent Set problem is defined as follows.


	 Independent Set 

	 Input: A graph G;

	 Output: An independent set of maximum size in G.


Zuckerman <cit.> has proved that, unless P = NP, there is no polynomial  algorithm for the Independent Set problem for any ε > 0, where p is the number of vertices in G.


	The problem Max Sync Set for weakly acyclic n-state automata over an alphabet of cardinality O(n) cannot be approximated in polynomial time within a factor of O(n^1 - ε) for any ε > 0 unless P = NP.

 We shall prove this theorem by constructing a gap-preserving reduction from the Independent Set problem. Given a graph G = (V, E), V = {v_1, v_2, …, v_p}, we construct an automaton A = (Q, Σ, δ) as follows. For each v_i ∈ V, we construct two states s_i, t_i in Q. We also add a state f to Q. Thus, |Q| = 2p + 1. The alphabet Σ consists of letters ṽ_1, …, ṽ_p corresponding to the vertices of G.
	
	The transition function δ is defined in the following way. For each 1 ≤ i ≤ p, the state s_i is mapped to f by the letter ṽ_i. For each v_iv_j ∈ E the state s_i is mapped to t_i by the letter ṽ_j, and the state s_j is mapped to t_j by the letter ṽ_i. All yet undefined transitions map a state to itself.
	
	 Let I be a maximum independent set in G. Then the set S = {s_i | v_i ∈ I}∪{f} is a synchronizing set of maximum cardinality (of size α(G) + 1) in the automaton A = (Q, Σ, δ). 
	
	 Let w be a word obtained by concatenating the letters corresponding to I in arbitrary order. Then w synchronizes the set S = {s_i | v_i ∈ I }∪{f} of states of cardinality |I| + 1. Thus, A has a synchronizing set of size at least α(G) + 1.
		
		In other direction, let w be a word synchronizing a set of states S' of maximum size in A. We can assume that after reading w all the states in S' are mapped to f, as all the sets of states that are mapped to any other state have cardinality at most two. Then by construction there are no edges in G between any pair of vertices in I' = {v_i | s_i ∈ S'}, so I' is an independent set of size |S'| - 1 in G. Thus the maximum size of a synchronizing set in A is equal to α(G) + 1. 
	
	Thus we have a gap-preserving reduction from the Independent Set problem to the Max Sync Set problem with a gap Θ(p^1 - ε) for any ε > 0. It is easy to see that n = Θ(p) and A is weakly acyclic, which concludes the proof of the theorem. 

Next we move to a slightly weaker inapproximability result for binary automata.


	The problem Max Sync Set for binary n-state automata cannot be approximated in polynomial time within a factor of O(n^1/2 - ε) for any ε > 0 unless P = NP.

 Again, we construct a gap-preserving reduction from the Independent Set problem extending the proof of Theorem <ref>. Given a graph G = (V, E), V = {v_1, v_2, …, v_p}, we construct an automaton A =(Q, Σ, δ) in the following way. Let Σ = {0, 1}. First we construct the main gadget A_main having a synchronizing set of states of size α(G). For each vertex v_i ∈ V, 1 ≤ i ≤ p, we construct a set of new states L_i = V_i ∪ U_i in Q, where V_i = {v^(i)_j : 1 ≤ j ≤ p}, U_i = {u^(i)_j : 1 ≤ j ≤ p}. We call L_i the ith layer of A_main. We also add a state f to Q. For each i, 1 ≤ i ≤ p, the transition function δ imitates choosing taking the vertices v_1, v_2, …, v_p into an independent set one by one and is defined as:
	
	
    δ(v^(i)_j, 0) = {[     u^(i)_j            ; v^(i + 1)_j            ;             ].

	
	
    δ(v^(i)_j, 1) = {[     u^(i)_j            ; v^(i + 1)_j            ;             ].

	
	Here all v^(n + 1)_j, 1 ≤ j ≤ p, coincide with f. For each state u^(i)_j, the transitions for both letters 0 and 1 lead to the originating state (i.e. they are self-loops).
	
	We also add an p-state cycle A_cycle attached to f. It is a set of p states c_1, …, c_p, mapping c_i to c_i + 1 and c_p to c_1 regardless of the input symbol. Finally, we set c_1  to coincide with f. Thus we get the automaton A_1. Figure <ref> presents an example of A_1 for a graph with three vertices v_1, v_2, v_3 and one edge v_2v_3.
	
	
	
	The main property of A_1 is claimed by the following lemma.
	
	
		The size of a maximum synchronizing set of states from the first layer in A_1 equals α(G).
	
	 Let I be a maximum independent set in G. Consider a word w of length p such that its ith letter is equal to 0 if v_i ∉ I and to 1 if v_i ∈ I. By the construction of A_1, this word synchronizes the set {v^(1)_j | v_j ∈ I}. Conversely, a synchronizing set of at least three states from the first layer can be mapped only to some vertex of A_cycle, and the corresponding set of vertices in G is an independent set. 
	
	Some layer in the described construction can contain a synchronizing subset of size larger than the maximum synchronizing subset of the first layer. To avoid that, we modify A_1 by repeating each state (with all transitions) of the first layer p times. More formally, we replace each pair of states v^(1)_j, u^(1)_j with p different pairs of states such that in each pair all the transitions repeat the transitions between v^(1)_j, u^(1)_j, and all the other states of the automaton. We denote the automaton thus constructed as A.
	
	The following lemma claims that the described procedure of constructing A from G is a gap-preserving reduction from the Independent Set problem in graphs to the Max Sync Set problem in binary automata.
	
	
		If α(G) > 1, then the maximum size of a synchronizing set in A is equal to pα(G) + 1.
	
	 Note that due to the construction of A_cycle, each synchronizing set of A is either a subset of a single layer of A together with a state in A_cycle or a subset of a set {v^(i)_j | 2 ≤ i ≤ℓ}∪{u^(ℓ)_j} for some ℓ and j, together with p new states that replaced v^(1)_j. Consider the first case. If some maximum synchronizing set S contains a state from the ith layer of A and i > 1, then its size is at most p + 1. A maximum synchronizing set containing some states from the first layer of A consists of pα(G) states from this layer (according to Lemma <ref>) and some state of A_cycle, so this set has size pα(G) + 1 ≥ 2p + 1. In the second case, the maximum size of a synchronizing set is at most p + (p - 1) + 1 = 2p < p α(G) + 1.
	
	
	It is easy to see that the constructed reduction is gap-preserving with a gap Θ(p^1 - ε) = Θ(n^1/2 - ε), where n is the number of states in A, as n = Θ(p^2). Thus the Max Sync Set for n-state binary automata cannot be approximated in polynomial time within a factor of O(n^1/2 - ε) for any ε > 0 unless P = NP, which concludes the proof of the theorem. 

Theorem <ref> can also be proved by using Theorem <ref> and a slight modification of the technique used in <cit.> for decreasing the size of the alphabet. However, in this case the resulting automaton is far from being weakly acyclic, while the automaton in the proof of Theorem <ref> has only one cycle. The next theorem shows how to modify our technique to prove an inapproximability bound for Max Sync Set in binary weakly acyclic automata.


	The Max Sync Set problem for binary weakly acyclic n-state automata cannot be approximated in polynomial time within a factor of O(n^1/3 - ε) for any ε > 0 unless P = NP.

 We modify the construction of the automaton A_main from Theorem <ref> in the following way. We repeat each state (with all transitions) of the first layer p^2 times in the same way as it is done in the proof of Theorem <ref>. Thus we get a weakly acyclic automaton A_wa with n = Θ(p^3) states, where p is the number of vertices in the graph G. Furthermore, similar to Lemma <ref>, the size of the maximum synchronizing set of states in A_wa is between p^2α(G) and p^2α(G) + p(p-1) + 1, because some of the states from the layers other than the first can be also mapped to f. Both of the values are of order Θ(p^2α(G)), thus we have an gap-preserving reduction providing the inapproximability within a factor of O(p^1 - ε) = O(n^1/3 - ε) for any ε > 0, where n is the number of states in A_wa.

We finish by noting that for two classes of automata the Max Sync Set problem is solvable in polynomial time.


	The problem Max Sync Set can be solved in polynomial time for unary automata.

 Consider the digraph G induced by states and transitions of an unary automaton A. By definition, each vertex of G has outdegree 1. Thus, the set of the vertices of G can be partitioned into directed cycles and a set of vertices not belonging to any cycle, but lying on a directed path leading to some cycle. Let n be the number of states in A. It is easy to see that after performing n transitions, each state of A is mapped into a state in some cycle, and all further transitions will not map any two different states to the same state. Thus, it is enough to perform n transitions and select such state s that the maximum number of states are mapped to s.

A more interesting case is covered by the following proposition. An automaton A = (Q, Σ, δ) is called Eulerian if there exists k such that for each state q ∈ Q there are exactly k pairs (q', a), q' ∈ Q, a ∈Σ, such that δ(q', a) = q.


	The problem Max Sync Set can be solved in polynomial time for Eulerian automata.


	According to Theorem 2.1 in <cit.> (see also <cit.> for the discussion of the Eulerian case), each word of minimum rank with respect to an Eulerian automaton synchronizes the sets S_1, S_2, …, S_r forming a partition of the states of the automaton into inclusion-maximal synchronizing sets. Moreover, according to this theorem all inclusion-maximal synchronizing sets in an Eulerian automaton are of the same size, thus each inclusion-maximal synchronizing set has maximum cardinality. A word of minimum rank with respect to an automaton can be found in polynomial time <cit.>, which concludes the proof.




§ COMPUTING THE RANK OF A SUBSET OF STATES


Assume that we know that the current state of the automaton A belongs to a subset S of its states. Even if it is not possible to synchronize S, it can be reasonable to minimize the size of the set of possible states of A, reducing the uncertainty of the current state as much as possible. One way to do it is to map S to a set S' of smaller size by applying some word to A. Recall that the size of the smallest such set S' is called the rank of S. Consider the following problem of finding the rank of a subset of states in a given automaton.


	 Set Rank 

	 Input: An automaton A and a set S of its states;

	 Output: The rank of S in A. 


The rank of an automaton, that is, the rank of the set of its states, can be computed in polynomial time <cit.>. However, since the automaton in the proof of PSPACE-completeness of Sync Set in <cit.> has rank 2 (and thus each subset of states in this automaton has rank either 1 or 2), it follows immediately that there is no polynomial c-approximation algorithm for the Set Rank problem for any c < 2 unless P = PSPACE. It also follows that checking whether the rank of a subset of states equals the rank of the whole automaton is PSPACE-complete. For monotonic weakly acyclic automata, this problem is hard to approximate within a factor of 9/8 - ϵ for any ϵ > 0 <cit.>. For general weakly acyclic automata it is possible to get much stronger bounds, as it is shown by the results of this section.

We shall need the Chromatic Number problem. A proper coloring of a graph G = (V, E) is a coloring of the set V in such a way that no two adjacent vertices have the same color. The chromatic number of G, denoted χ(G), is the minimum number of colors in a proper coloring of G. Recall that a set of vertices in a graph is called independent if no two vertices in this set are adjacent. A proper coloring of a graph can be also considered as a partition of the set of its vertices into independent sets.


	 Chromatic Number

	 Input: A graph G;

	 Output: The chromatic number of G.


This problem cannot be approximated within a factor of O(p^1 - ϵ) for any ϵ > 0 unless P = NP, where p is the number of vertices in G <cit.>.


	The Set Rank problem for n-state weakly acyclic automata with alphabet of size O(√(n)) cannot be approximated within a factor of O(n^1/2 - ϵ) for any ϵ > 0 unless P = NP.


	We shall prove this theorem by constructing a gap-preserving reduction from the Chromatic Number problem, extending the technique in the proof of Theorem <ref>. Given a graph G = (V, E), V = {v_1, v_2, …, v_p}, we construct an automaton A = (Q, Σ, δ) as follows. The alphabet Σ consists of letters ṽ_1, …, ṽ_p corresponding to the vertices of G, together with a switching letter ν. We use p identical synchronizing gadgets T^(k), 1 ≤ k ≤ p, such that each gadget synchronizes a subset of states corresponding to an independent set in G. Gadget T^(k) consists of a set {s^(k)_i, t^(k)_i | 1 ≤ i ≤ p}∪{f^(k)} of states.
	
	The transition function δ is defined as follows. For each gadget T^(k), for each 1 ≤ i ≤ p, the state s^(k)_i is mapped to f^(k) by the letter ṽ_i. For each v_iv_j ∈ E the state s^(k)_i is mapped to t^(k)_i by the letter ṽ_j, and the state s^(k)_j is mapped to t^(k)_j by the letter ṽ_i. All yet undefined transitions corresponding to the letters ṽ_1, …, ṽ_p map a state to itself.
	
	It remains to define the transitions corresponding to ν. For each 1 ≤ k ≤ p - 1, ν maps t^(k)_i and s^(k)_i to s^(k + 1)_i, and f^(k) to itself. Finally, ν acts on all states in T^(p) as a self-loop.
	
	Define S = {s^(1)_i | 1 ≤ i ≤ p}. We shall prove that the rank of S is equal to the chromatic number of G. Consider a proper coloring of G with the minimum number of colors and let I_1 ∪…∪ I_χ(G) be the partition of G into independent sets defined by this coloring. For each I_j, consider a word w_j obtained by concatenating the letters corresponding to the vertices in I_j in some order. Consider now the word w_1 ν w_2 ν…ν w_χ(G). This word maps the set S to the set {f^(i)| 1 ≤ i ≤χ(G)}, which proves that the rank of S is at most χ(G).
	
	In the other direction, note that after each reading of ν all states except f^(k), 1 ≤ k ≤ p - 1, are mapped to the next synchronizing gadget (except the last gadget T^(p) which is mapped to itself). By definition of δ, only a subset of states corresponding to an independent set of vertices can be mapped to some particular f^(k), and the image of S after reading any word is a subset of the states in some gadget together with some of the states f^(k), 1 ≤ k ≤ p. Hence, the rank of S is at least χ(G).
	
	Thus we have a gap-preserving reduction from the Chromatic Number problem to the Set Rank problem with gap Θ(p^1 - ε) for any ε > 0. It is easy to see that n = Θ(p^2), A is weakly acyclic and its alphabet has size O(√(n)), which finishes the proof of the theorem.
	 

Using the classical technique of reducing the alphabet size (see <cit.>), O(n^1/3 - ϵ) inapproximability can be proved for binary automata. To prove the same bound for binary weakly acyclic automata, we have to refine the technique of the proof of the previous theorem.


	The Set Rank problem for n-state binary weakly acyclic automata cannot be approximated within a factor of O(n^1/3 - ϵ) for any ϵ > 0 unless P = NP.


 To prove this theorem we construct a gap-preserving reduction from the Chromatic Number problem, extending the proof of the previous theorem.
	
	Given a graph G = (V, E), V = {v_1, v_2, …, v_p}, we construct an automaton A =(Q, {0, 1}, δ). In our reduction we use two kinds of gadgets: p synchronizing gadgets T^(k), 1 ≤ k ≤ p, and p waiting gadgets R^(k), 1 ≤ k ≤ p. Gadget T^(k) consists of a set {v_i,j^(k)| 1 ≤ i,j ≤ p}  of states, together with a state f^(k), and R^(k), 1 ≤ k ≤ p, consists of the set {u_i,j^(k)| 1 ≤ i, j ≤ p}.
	
	For each i, j, k, 1 ≤ i, j, k ≤ p, the transition function δ is defined as:
	
	
    δ(v^(k)_i, j, 0) = {[     u^(k)_i,j              ; v^(k)_i + 1,j              ;               ].

	
	
    δ(v^(k)_i,j, 1) = {[     u^(k)_i,j              ; v^(k)_i + 1,j              ;               ].

	
	Here all v^(k)_p + 1,j, 1 ≤ j ≤ p, coincide with f^(k). We set δ(u^(k)_i,j, x) = u^(k)_i + 1,j for x ∈{0, 1}, 1 ≤ i, k ≤ p - 1, 1 ≤ j ≤ p, and δ(u^(k)_p, j, x) = v^(k + 1)_1,j for 1 ≤ j ≤ p, 1 ≤ k ≤ p - 1, x ∈{0, 1}. The states u^(p)_i,j are sink states: both letters 0 and 1 act on them as self-loops. Finally, we set S = {v^(1)_1, j| 1 ≤ j ≤ p}. Figure <ref> gives an idea of the described construction.
	
		
		
	
	The idea of the presented construction is essentially a combination of the ideas in the proofs of Theorems <ref> and <ref>, so we provide only a sketch of the proof. A synchronizing gadget T^(k) synchronizes a set S^(k)⊆ S of states corresponding to some independent set in G. All the states corresponding to the vertices adjacent to vertices corresponding to S^(k) are mapped to the corresponding waiting gadget R^(k), and get to the next synchronizing gadget T^(k + 1) only after the states of S^(k) are synchronized (and thus mapped to f^(k)). Hence, the minimum size of a partition of V into independent sets is equal to the rank of S.  The number of states in A is O(p^3). Thus, we get Θ(n^1/3 - ϵ) inapproximability.
	 









§ SUBSET SYNCHRONIZATION


In this section, we obtain complexity results for several problems related to subset synchronization in weakly acyclic automata. We adapt Eppstein's construction from <cit.>, which is a powerful and flexible tool for such proofs. We shall need the following NP-complete SAT problem <cit.>.


	 SAT 

	 Input: A set X of n boolean variables and a set C of m clauses;

	 Output: Yes if there exists an assignment of values to the variables in X such that all clauses in C are satisfied, No otherwise.



	The Sync Set problem in binary weakly acyclic automata is NP-complete.


	Because of the polynomial upper bound on the length of a shortest word synchronizing a subset of states proved in Proposition <ref>, we can use such word as a certificate. Thus, the problem is in NP.
	
	We reduce the SAT problem. Given X and C, we construct an automaton A =(Q, {0, 1}, δ). For each clause c_j, we construct n + 1 states y^(j)_i, 1 ≤ i ≤ n + 1, in Q. We introduce also a state f ∈ Q. The transitions from y^(j)_i correspond to the occurrence of x_i in c_j in the following way: for 1 ≤ i ≤ n, 1 ≤ j ≤ m, δ(y^(j)_i, a) = f if the assignment x_i = a, a ∈{0, 1}, satisfies c_j, and δ(y^(j)_i, a) = y^(j)_i + 1 otherwise. The transition function δ also maps y^(j)_n + 1 to itself for all 1 ≤ j ≤ m and both letters 0 and 1.
	
	Let S = {y^(j)_1 | 1 ≤ j ≤ m}. The word w = a_1 a_2 … a_n synchronizes S if a_i is the value of x_i in an assignment satisfying C, and vice versa. Thus, the set is synchronizing if and only if all clauses in C can be satisfied by some assignment of binary values to the variables in X. 
	 

By identifying the states y^(j)_n + 1 for 1 ≤ j ≤ m and adding f to S it is also possible to prove that the problem of checking whether the rank of a subset of states equals the rank of an automaton is coNP-complete for binary weakly acyclic automata (cf. the remarks in the beginning of Section <ref>).

The proof of Theorem <ref> can be used to prove the hardness of a special case of the following problem, which is PSPACE-complete in general <cit.> and NP-complete for weakly acyclic monotonic automata over a three-letter alphabet <cit.>.


	 Finite Automata Intersection 

	 Input: Automata A_1, …, A_k (with initial and accepting states); 

	 Output: Yes if there is a word which is accepted by all automata, No otherwise.



	Finite Automata Intersection is NP-complete when all automata in the input are binary weakly acyclic.

 Observe first that if there exists a word which is accepted by all automata, then a shortest such word w has length at most linear in the total number of states in all automata. Indeed, for each automaton consider a topological sort of the set of its states. Each letter of w maps at least one state in some automaton to some other state, which has larger index in the topological sort of the set of states of this automaton. Thus, the considered problem is in NP.
	
	For the hardness proof, we use the same construction as in Theorem <ref>. Provided X and C, define A in the same way as in Theorem <ref>. Define A_j = (Q_j, {0, 1}, δ_j) as follows. Take Q_j = {y^(j)_i, 1 ≤ i ≤ n + 1 }∪{f} and δ_j to be the restriction of δ to the set Q_j. Set y^(j)_1 to be the input state and f to be the only accepting state of A_j. Then there exists a word accepted by automata A_1, …, A_m if and only if all clauses in C are satisfiable by some assignment.
	 







To obtain the next results, we shall need a modified construction of the automaton from the proof of Theorem <ref>, as well as some new definitions. A partial automaton is a triple (Q, Σ, δ), where Q and Σ are the same as in the definition of a finite deterministic automaton, and δ is a partial transition function (i.e., a transition function which may be undefined for some argument values). Given an instance of the SAT problem, construct a partial automaton A_base = (Q, {0, 1}, δ) as follows. We introduce a state f ∈ Q. For each clause c_j, we construct n + 1 states y^(j)_i, 1 ≤ i ≤ n + 1, in Q. For each c_j, construct also states z^(j)_i for h_i + 1 ≤ i ≤ n + 1, where h_i is the smallest index of a variable occurring in c_j. The transitions from y^(j)_i correspond to the occurrence of x_i in c_j in the following way: for 1 ≤ i ≤ n, δ(y^(j)_i, a) = z^(j)_i + 1 if the assignment x_i = a, a ∈{0, 1}, satisfies c_j, and δ(y^(j)_i, a) = y^(j)_i + 1 otherwise. For x ∈{0, 1}, we set δ(z^(j)_i, a) = z^(j)_i + 1 for h_i + 1 ≤ i ≤ n, 1 ≤ j ≤ m, a ∈{0, 1}. The transition function δ also maps z^(j)_n + 1, 1 ≤ j ≤ m, and f to f for both letters 0 and 1.

A word w is said to carefully synchronize a partial automaton A if it maps all its states to the same state q, and each mapping corresponding to a prefix of w is defined for each state. The automaton A is then called carefully synchronizing. We use A_base to prove the hardness of the following problem.


	 Careful Synchronization 

	 Input: A partial automaton A; 

	 Output: Yes if A is carefully synchronizing, No otherwise.


For binary automata, Careful Synchronization is PSPACE-complete <cit.>. For monotonic automata over a four-letter alphabet it is NP-hard. We call a partial automaton aperiodic if for any word w ∈Σ^* and any state q ∈ Q there exists k such that either δ(q, w^k) is undefined, or δ(q, w^k) = δ(q, w^k + 1).


	Careful Synchronization is NP-hard for aperiodic partial automata over a three-letter alphabet.


	We reduce the SAT problem. Given X and C, we first construct A_base. Then we add an additional letter r to the alphabet of A_base and introduce m new states s^(m). For 1 ≤ i ≤ n, 1 ≤ j ≤ m, we define δ(s^(j), r) = y^(j)_1, δ(y^(j)_i, r) = y^(j)_1, δ(z^(j)_i, r) = y^(j)_1, δ(f, r) = f. All other transitions are left undefined. Let us call the constructed automaton A.
	
	The automaton A is carefully synchronizing if and only if all clauses in C can be satisfied by some assignment of binary values to the variables in X. Moreover, the word w = r w_1 w_2 … w_n 0, is carefully synchronizing if w_i is the value of x_i in such an assignment.
	
	Indeed, note that the first letter of w is necessarily r, as it is the only letter defined for all the states. Moreover, each word starting with r maps Q to a subset of {y^(j)_i, z^(j)_i | 1 ≤ j ≤ m + 1}∪{f}. The only way for a word to map all states to f is to map them first to the set {z^(j)_n + 1| 1 ≤ j ≤ m}, because there are no transitions defined from any y^(j)_n + 1, except the transitions defined by r. But this exactly means that there exists an assignment satisfying C.
	
	The constructed automaton is aperiodic, because each cycle which is not a self-loop contains exactly one letter r.
	 

The complexity of the following problem can be obtained from Theorem <ref>.


	 Positive Matrix

	 Input: A set M_1, …, M_k of n × n binary matrices; 

	 Output: Yes if there exists a sequence M_i_1×…× M_i_k of multiplications (possibly with repetitions) providing a matrix with all elements equal to 1, No otherwise.



	Positive Matrix is NP-hard for two upper-triangular and two lower-triangular matrices.


	The proof uses the idea from <cit.>. Consider three transition matrices corresponding to the letters of the automaton constructed in the proof of Theorem <ref>. Add the matrix corresponding to the letter mapping the state f to all states and undefined for all other states. Any sequence of matrices resulting in a matrix with only positive elements must contain the new matrix, and before that there must be a sequence of matrices corresponding to a word carefully synhronizing the automaton from the proof of Theorem <ref>. Thus we get a reduction from Careful Synchronization for aperiodic partial automata over a three-letter alphabet to Positive Matrix. It is easy to see that the reduction uses two upper-triangular and two lower-triangular matrices.


Finally, we show the hardness of the following problem (PSPACE-complete in general <cit.>).


	 Subset Reachability 
 
	 Input: An automaton A = (Q, Σ, δ) and a subset S of its states; 

	 Output: Yes if there exists a word w such that {δ(q, w) | q ∈ Q} = S, No otherwise.



	Subset Reachability is NP-complete for weakly acyclic automata.

 Consider a topological sort of Q.  Let w be a shortest word mapping Q to some reachable set of states. Then each letter of w maps at least one state to a state with a larger index in the topological sort. Thus w has length O(|Q|^2), since the maximum total number of such mappings is (|Q| - 1) + (|Q| - 2) + … + 1 + 0. Thus, the considered problem is in NP.
	
	For the NP-hardness proof, we again reduce the SAT problem. Given an instance of SAT, construct A_base first. Next, add a transition δ(y^(j)_n + 1, a) = f for 1 ≤ j ≤ m, a ∈{0, 1}, resulting in a deterministic automaton A.
	
	Similar to the proof of Theorem <ref>, C is satisfiable if and only if the set {z^(n + 1)_j | 1 ≤ j ≤ m}∪{f} is reachable in A. 
	 



§ CONCLUSIONS AND OPEN PROBLEMS


As shown in this paper, weakly acyclic automata serve as an example of a small class of automata where most of the synchronization problems are still hard. More precisely, switching from general automata to weakly acyclic usually results in changing a PSPACE-complete problem to a NP-complete one.

Some problems for weakly acyclic automata are still open. One of them is to study the approximability of the Shortest Sync Word problem: there is a drastic gap between known inapproximability results and the O(n)-approximation algorithm for general automata. Another natural problem is to study the Max Sync Set and Set Rank problems complexity in strongly connected automata. The technique used by Vorel for proving PSPACE-completeness of the Sync Set problem in strongly connected automata seems to fail here.



  §.§.§ Acknowledgments


We would like to thank Peter J. Cameron for introducing us to the notion of synchronizing automata, and Vojtěch Vorel, Yury Kartynnik, Vladimir Gusev and Ilia Fridman for very useful discussions. We also thank Mikhail V. Volkov and anonymous reviewers for their great contribution to the improvement of the paper.


	alpha
	
