# synchronization_and_diversity_of_solutions__6e8d671d.pdf Synchronization and Diversity of Solutions Emmanuel Arrighi1, Henning Fernau2, Mateus de Oliveira Oliveira1,3, Petra Wolf 1,2 1 University of Bergen, Bergen, Norway 2 University of Trier, Trier, Germany 3 Stockholm University, Stockholm, Sweden emmanuel.arrighi@uib.no, oliveira@dsv.su.se, mail@wolfp.net, fernau@uni-trier.de A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1, w2, . . . , wr} L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution. 1 Introduction A word w is said to be synchronizing for a deterministic finite automaton (DFA) A if there is some state q of A such that any state q is sent to q by w. This concept has found numerous applications across several subfields of computer science and artificial intelligence, such as circuit testing (Hennie 1964; Kohavi and Jha 2009; Sandberg 2005), multi-agent systems (Chapman and Mesbahi 2014; Chevalier, Hendrickx, and Jungers 2015), robotics (Natarajan 1986), game theory (Maubert 2009), among others. The most central problem in the field of synchronization is the one to determine whether a given DFA has a synchronizing word. Note that this problem can be decided in polynomial time (Starke 1966). Nevertheless, in several applications, one is interested in finding a synchronizing word satisfying certain additional constraints (Fernau et al. 2019; Wolf 2020; T urker and Yenig un 2015). Here, the complexity landscape of the problem changes drastically: even the problem of determining the existence of a synchronizing word satisfying certain additional regularity constraints is NP-hard. Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. For instance, it is NP-hard to determine whether a given DFA A has a synchronizing word that belongs to the regular language ab a (Fernau et al. 2019), or whose length is bounded by a given integer (Rystsov 1980; Eppstein 1990). Diversity of solutions is a trend that has been calling substantial attention of the artificial intelligence community during the past years (Hebrard et al. 2005; Baste et al. 2019; Petit and Trapp 2019; Baste et al. 2020; Fomin et al. 2020; Ingmar et al. 2020; Arrighi et al. 2021). The goal is to find not a single solution to a given combinatorial problem, but rather a small set of solutions being sufficiently diverse from each other. One of the motivations for this framework is that it can be applied in situations where certain side constraints are difficult, or even impossible to formalize. In this case, the user can select a solution that she deems to be best for her application at hand. Intuitively, the diversity requirement tells us that the solutions that are given as an output are a reasonable representative of the space of solutions.1 Also, small sets of solutions make sense because one does not want to overwhelm the user with an excessive number of solutions. While for many combinatorial problems, notions of solution diversity based on the Hamming distance between pairs of solutions are sufficient, in the context of synchronization, these notions are not so appropriate. First, distinct solutions may have distinct length, and it is not clear how positions should be aligned in order to define an appropriate notion of Hamming distance. Additionally, even strings of the same size that are very similar to each other may have very large Hamming distance. For instance, the Hamming distance between the string w = abab...ab = (ab)n and the string w = baba...ba = (ba)n is 2n, while w can be transformed into w with two modifications: first delete the first symbol of w and then append the symbol a to the resulting string. We circumvent this issue by basing our diversity measure on the notion of string edit distance (Wagner and Fischer 1974; Levenshtein 1966). This is a well studied metric for strings with nice properties and applications in a wide variety of fields (Bunke and Csirik 1995; Lyras, Sgarbas, and Fakotakis 2007; Chua, Marsland, and Guesgen 2011). Another issue is that sets of solutions in which any two of them are far apart from each other may still not capture solu- 1See (Sayin 2000; Vaz et al. 2015; Demirovic and Schwind 2020) for further discussions. The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23) tion diversity in the context of synchronization. The problem is that if w is a synchronizing word, then any superword of w is also synchronizing. Therefore, any sequence of superwords w1, w2, . . . , wk of w of substantially distinct lengths would have large diversity if only edit distance were taken into consideration. To circumvent this issue, we require that each word in the set of solutions is subsequence-minimal with respect to the synchronization requirement. The subsequence minimality requirement combined with edit distance not only guarantees that solutions in any given subset are genuinely distinct, but also provides a way of tackling diverse synchronization problems using the machinery of finite automata theory. On the one hand, Higman s lemma (Higman 1952) (see Lemma 6), a classical tool in automata theory, implies that the set of subsequence-minimal synchronizing words in the language of an automaton is always finite. On the other hand, the computation of the edit distance between two words is a process that can be simulated using finite automata. More specifically, it is possible to construct finite automata accepting a suitable encoding of pairs of words that are far apart from each other. Note that subsequence-minimal synchronization problems involving a single DFA A are already hard. First, subsequence-minimal synchronizing words for a DFA A may have exponential length on the number of states of A (Proposition 20). Second, determining if a given word w is subsequence-minimal among all synchronizing words in the language of a DFA A is co NP-hard (Theorem 19). Third, determining if a DFA A has two distinct subsequenceminimal synchronizing words is NP-hard (Theorem 23). Finally, the problem of enumerating the set of subsequenceminimal synchronizing words is #P-hard (Theorem 24). In order to cope with the inherent intractability of synchronization problems, we leverage on the framework of parameterized complexity theory (Downey and Fellows 1999). In particular, we show that for each fixed value of r, interesting computational problems requiring a diverse set with r subsequence-minimal synchronizing words can be solved in time that is fixed-parameter tractable with respect to the size of the synchronizing automaton A. Previously, algorithms with an FPT dependence in |A| were unknown even for r = 2! Using our approach, we also show that given a DFA A with state set Q over an alphabet Σ and a word w Σ , one can determine in time O(f(|Σ|, |Q|) |w|), for some function f, if some subsequence-minimal synchronizing word for A is a subsequence of w, and we can construct such a subsequence in case the answer is affirmative (Theorem 15). As mentioned above, the unparameterized version of this problems is already co NP-hard. Our main result (Theorem 16) states that given numbers r, k N, a DFA A, and an possibly nondeterministic finite automaton B over an alphabet Σ, the problem of computing a subset {w1, . . . , wr} L(B) of subsequence-minimal synchronizing words for A, with pairwise edit distance of at least k, can be solved in time O(f A(r, k) |B|r log(|B|)) for some suitable function f depending only on A, r and k. Intuitively, the automaton A is a specification of a system which we want to synchronize (or reset), and B is a specification of the set of words that are allowed to be used as synchronizing sequences. As stated in the beginning of this section, the unparameterized version of this problem is NP-hard even if we are interested in finding a single solution and the language of the automaton B is as simple as ab a. As a consequence of our main result, given a word w Σ , the problem of determining whether there exist r subsequence-minimal synchronizing words for A that are subsequences of w and that are at least k apart from each other can be solved in time O(f A(r, k) |w|r log(|w|)) (Corollary 17). It turns out that our notion of diversity of solutions is general enough to be applied in other contexts where solutions are strings whose sizes may have to vary. In particular, we generalize our framework to the realm of conformant planning (Theorem 28), where the goal is to design plans that achieve goals irrespectively of initial conditions and of nondeterminism that may occur during the execution of these plans (Anders 2019; Bonet 2010; Cimatti, Roveri, and Bertoli 2004; Palacios and Geffner 2009). Further Applications. In the full version of this work (see https://doi.org/10.5281/zenodo.7384348), we discuss applications of our main results to several subdomains of artificial intelligence, such as multi-agent systems, robotics, secret sharing, and others. The intuition is that synchronizing words may be viewed as a way of resetting agents whose behavior are modeled by finite automata, while diversity may be interpreted as a way of achieving resilience (if one synchronizing word fails, we may still use another one), distributivity (multiple synchronizing words may be distributed among distinct parties), or security (multiple synchronizing words may be used to define secret-sharing protocols). 2 Preliminaries Let N denote the set of non-negative integers, while N>0 is the set of positive integers. For an integer k N, we denote by [k] the set {1, 2, . . . , k}. Hence, [0] = . For n N, Σn denotes the set of all words of length n. We denote Σ+ = S n N>0 Σn and Σ = Σ+ {ε}, where ε denotes the empty word. Hence, Σ is the groundset of the free monoid generated by Σ; its binary operation is known as concatenation, often denoted by juxtaposition, but sometimes highlighted by explicitly writing . Given a word w Σ , we let |w| denote the length of w. For each i 1, . . . , |w|, we let w[i] denote the i-th symbol of w. For i, j 1, . . . , |w|, we let w[i..j] denote the infix w[i]w[i + 1] . . . w[j]. A deterministic finite automaton (DFA) A is a tuple A = (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is a finite alphabet, δ: Q Σ Q is a total function called the transition function of A, q0 Q is the start state, and F Q is a set of final states. For synchronization problems, we sometimes omit start and final states of DFAs. When speaking about the complexity of algorithms involving a DFA A, we sometimes use |A| to denote the number of bits needed to specify A; for convenience, let |A| = |Q| |Σ| log(|Q|) (for DFAs). Often, |Q| is sufficient as a size estimate. We generalize δ to words by setting δ(q, ε) = q and δ(q, w) = δ(δ(q, w[1]), w[2..|w|]). We further generalize δ to sets of states S Q and sets of input letters Γ Σ as δ(S, Γ) = {δ(s, γ) | s S, γ Γ}, or to words w as δ(S, w) = {δ(s, w) | s S}. We say a word w Σ is a synchronizing word for A if |δ(Q, w)| = 1. We assume basic knowledge of automata theory on side of the reader. In particular, the product automata construction for finite automata should be known. Also, we make use of nondeterministic finite automata (or NFA for short) without a precise formal definition. Recall that with NFAs, the transition function is replaced by a transition relation δ. Due to the well-known powerset automaton construction, we can (still) view δ as mapping (S, w) to T, where S, T are sets of states, and w is a word over the input alphabet. We will discuss several partial orderings on Σ now. See (Birget 1993) for a review of these and other concepts. In particular, x is a prefix of y, written x y, if y xΣ , x is a suffix of y if y Σ x and x is an infix of y, written x y, if y Σ xΣ . We say that x is a subsequence of y, written x y,2 if there exists a sequence of indices i1 < i2 < ... < i|x| such that for each j [|x|], yij = xj. If we add the word proper, we exclude the possibility that x = y in each of the previous definitions. In our notations, we then write , , or <, respectively. A non-empty word x can be split into the prefix x[1] of length 1 and the suffix of length |x| 1 that we call (reminiscent of Prolog) the tail of x, denoting it by tail(x). Hence, x = x[1]tail(x). Let Σ be some alphabet not containing the symbol that we will now use as a blank symbol. For k N>0 , define (Σ { }) k = (Σ { })k \ {( , . . . , )} as a new alphabet with (|Σ| + 1)k 1 many symbols that we also call compound characters, consisting of k letters. Of particular importance will be the case k = 2. For this, we now define a specific construction, called convolution, that takes two words u, v Σ and constructs a unique word w = u v over the alphabet (Σ { }) 2, in a recursive fashion as follows. ε, if u = v = ε (u[1], ) (tail(u) ε), if u = ε, v = ε ( , v[1]) (ε tail(v)), if u = ε, v = ε (u[1], v[1]) (tail(u) tail(v)), if u = ε, v = ε For instance, the convolution of word u = ababa with v = abb is the word u v = (a, a)(b, b)(a, b)(b, )(a, ). This operation can be generalized to the convolution of k > 2 words in a straightforward manner. Lemma 1. The language of all words over the alphabet (Σ { }) k that can be obtained as the convolution of k words over Σ can be accepted by a DFA with 2k many states. The previous construction can be integrated into the classical product automaton construction to give the following result. Corollary 2. Let A = (Q, Σ, δ, q0, F) be a DFA. Let Ak be a DFA accepting the set of all strings of the form u1 u2 uk, where for each l [k], ul L(A). Then, Ak needs to have no more than (2|Q|)k many states. A similar statement holds for NFAs. 2In the literature, the naming of these relations is rather confusing. Infixes are known as factors or subwords, subsequences are also called (scattered) subwords. 3 Diversity in Synchronization We will base our notion of diversity on the notion of edit distance between strings, as it provides a suitable way of measuring dissimilarity between strings with possibly distinct lengths. Let u = u[1]u[2] . . . u[n] be a string in Σ. We define the following elementary edit operations on u; see (Levenshtein 1966; Wagner and Fischer 1974). 1. Insertion: for i {0, . . . , n}, insert letter a Σ after position i, yielding u[1..i] a u[i + 1..n]. 2. Deletion: for i {1, . . . , n}, delete the entry u[i] from u, resulting in u[1..i 1] u[i + 1..n]. 3. Replacement: for i {1, . . . , n}, replace u[i] with some a Σ \ {u[i]}, getting u[1..i 1] a u[i + 1..n]. We say that a string u Σ can be edited to a string w Σ in s steps if there is some sequence u0, u1, . . . , us of strings in Σ such that for each j [r], uj is obtained from uj 1 by the application of one of the three elementary edit operations above and u = u0, w = us. Definition 3 (Edit Distance). The edit distance between u and w, denoted by (u, w), is defined as the minimum s such that u can be edited to w in s steps. Intuitively, the edit distance between u and w is the minimum number of insertions, deletions and replacements necessary to transform u into w. By classical results, this distance (and related ones) can be computed efficiently; see (Wagner and Fischer 1974; Wagner 1975). As discussed in the introduction, each word containing a synchronizing word as an infix is also synchronizing. Hence, in order to get a diverse set of synchronizing words, we need to demand minimality with respect to the subsequence order.3 A word w is a subsequence-minimal synchronizing word for a DFA A if w is synchronizing for A and no proper subsequence w of w is synchronizing for A. On the one hand, one can ensure that the set of subsequence-minimal synchronizing words for a DFA is finite (see Sec. 4). On the other hand, subsequence minimality imposes a higher level of dissimilarity between two words in a prospective subset W of solutions, increasing the representativeness of W. Definition 4 (Synchronization Diversity). Let A = (Q, Σ, δ) be a DFA. We say that a set of words {w1, . . . , wr} has synchronization diversity k if the following holds. 1. For each i, j {1, ..., r} with i = j, (wi, wj) k. 2. For each i {1, ..., r}, wi is a subsequence-minimal synchronizing word for A. 4 Subsequence Minimality The next well-known lemma, whose proof can be found in (Gruber, Holzer, and Kutrib 2007, Corollary 18), states that, given an NFA A, one can construct a finite automaton Subseq(A) accepting precisely the subsequences of words in L(A). As shown in (Gruber, Holzer, and Kutrib 2007, Lemma 19), this bound cannot be improved in general. 3One is tempted to require infix minimality instead, but as the infix order is not a well-ordering, the set of infix-minimal synchronizing words of an automaton can be infinite, which make it difficult to find good representatives for the space of solutions. Lemma 5 (Subsequence Automaton). Let A = (Q, Σ, δ) be an NFA. One can construct in time O(|A|) an NFA Subseq(A) with |Q| states with L(Subseq(A)) = {u : w L(A), u w}. If A has a trap state, Subseq(A) has |Q| 1 states. A classic result in partial order theory, known as Higman s Lemma, states that for each finite set Σ, the set Σ of finite words over Σ is well-ordered under the subsequence order (Higman 1952). An interesting consequence of this lemma is the fact that for each language L Σ , the set of subsequence-minimal words in L is finite. For a more language-theoretic treatment, refer to (Haines 1969). Lemma 6 (Higman s Lemma). Let Σ be an alphabet and L Σ . There is a unique finite set S L satisfying the following properties. 1. For each word w L, some word u S is a subsequence of w. 2. Each word u S is subsequence-minimal for L. It is worth noting that Lemma 6 holds with respect to any language L Σ , irrespectively of whether L is regular or not. Nevertheless, if we are given a DFA A accepting L, then we can construct a DFA Min Subseq(A) accepting the set of subsequence-minimal words for L. Lemma 7 (Subsequence-Minimal Words, Theorem 2.1(3) of (Birget 1993)). Let A = (Q, Σ, δ) be a DFA. One can construct in time O(2|Q| |A|) a DFA Min Subseq(A) with at most |Q| 2|Q| many states accepting the language L(Min Subseq(A)) = {u : u L(A) w L(A), w < u}. Interestingly, the exponential blow-up in the number of states of the input automaton A is unavoidable, even if one allows Min Subset(A) to be an NFA. Here, we refer to Example 3.18, Facts 3.19 and 3.20 in (Birget 1993). The next lemma states that given an automaton A, one can construct a DFA Sync(A) accepting precisely the words in Σ that are synchronizing for A. This is shown by using the classical subset construction, now on a DFA A; see (Sandberg 2005; Volkov 2008). Lemma 8 (Synchronizing Words). Let A = (Q, Σ, δ) be a DFA. One can construct in time O(2|Q| |A|) a DFA Sync(A) with at most 2|Q| states such that L(Sync(A)) = {u : u is synchronizing for A}. This exponential blow-up is necessary, as recently proven in (Hoffmann 2021). By combining Lemma 8 with Lemma 7, we have the following corollary stating that, given a DFA A, one can construct a DFA Sync Min Subseq(A) of state complexity at most double-exponential in the state complexity of A accepting the set of subsequence-minimal synchronizing words for A. It is an interesting open question if this double-exponential blow-up is necessary. Corollary 9. Let A = (Q, Σ, δ) be a DFA. One can construct in time O(22|Q| 2|A|) a DFA Sync Min Subseq(A) with at most 22|Q|+|Q| many states accepting the language L(Sync Min Subseq(A)) = {u : u is a subsequence-minimal synchronizing word for A}. 5 Edit Distance vs Diversity of Solutions In (Wagner and Fischer 1974), a dynamic-programming algorithm is given that efficiently computes the edit distance between two given strings. Edit distance questions are an active area of study, as exemplified by (Bringmann et al. 2019). Ignoring technicalities, the next lemma can be seen as an automata-theoretic counterpart of such computations. Lemma 10. Let Σ be an alphabet and k N>0. There is an NFA Edit<(Σ, k) with 2O(k log |Σ|) many states that accepts L(Edit<(Σ, k)) = {u w : (u, w) < k}. (1) As a corollary of Lemma 10, by first determinizing the automaton of the previous lemma and then (basically) complementing final states, plus checking (by a product automaton construction) that words come from convolutions of words, using Lemma 1, we get the following result. Lemma 11. Let Σ be an alphabet and k N>0. There is a DFA Edit (Σ, k) with 22O(k log |Σ|) states accepting L(Edit (Σ, k)) = {u w : (u, w) k}. (2) Let W Σ be a finite set of strings. The min-diversity of W, denoted by Min Div(W) is defined as the minimum edit distance among any pair of strings in W. Min Div(W) = min u,w W (u, w) (3) Next, we state that given DFA A, one can construct a DFA Min Div(A, r, k) whose language is a suitable encoding of all r-tuples of words from L(A) with diversity at least k. Lemma 12. Let A = (Q, Σ, δ, q0, F) be DFA over Σ. For each r, k N+, one can construct a DFA Min Div(A, r, k) with 2r2 2O(k log |Σ|) |Q|r many states for the language of all compound words u1 ur (Σ { }) r that satisfy i [r](ui L(A)) Min Div({u1, . . . , ur}) k. Its construction takes O 2r2 2O(k log |Σ|) |A|r time. Proof. Let [r] 2 = {{i, j} : i, j [r], i = j}. For each pair {i, j} [r] 2 , let Edit i,j(Σ, k) be the automaton that accepts all strings of the form u1 u2 ur where for each l [r], ul Σ+ and (ui, uj) k, based on Lemma 11. Let Ar be the automaton accepting the set of all strings of the form u1 u2 ur where for each l [r], ul L(A). Then, Min Div(A, r, k) can be defined as the automaton that accepts the intersection of the languages L(Ar) with the languages L(Edit i,j(Σ, k)) for {i, j} [r] 2 . This implies that the number of states in Min Div(A, r, k) is at most the product of the number of states of Ar with the number of states of Edit i,j(Σ, k)) for {i, j} [r] 2 . According to Corollary 2, the DFA Ar has at most (2|Q|)r + 1 states. Its construction costs O(|A|r) time. We claim below that one can define Edit i,j(Σ, k)) in such a way that it has at most 22O(k log |Σ|) states. As a consequence, one can construct Min Div(A, r, k) in such a way that it has 2r2 2O(k log |Σ|) |Q|r states. Its construction takes O(2r2 2O(k log |Σ|) |A|r) time. Let ρi,j : Σ k Σ 2 be the map that sends each tuple (a1, a2, . . . , ar) to the pair (ai, aj). Then, the automaton Edit i,j(Σ, k) can be defined as the automaton that accepts the inverse homomorphic image of L(Edit (Σ, k)) under ρi,j. More specifically, the automaton Edit i,j(Σ, k) is constructed from Edit (Σ, k) by replacing each transition (q, (a, b), q ) with the set of transitions {(q, (a1, . . . , ar), q ) : (a1, . . . , ar) Σ r, ai = a, aj = b}. Note that since no new states are created, the number of states in Edit i,j(Σ, k) is equal to the number of states in Edit (Σ, k), that is, 22O(k log |Σ|) (Lemma 11). 6 Algorithmic Results In this section, we state and prove our main results, starting with two preparatory observations. Proposition 13 (Single-Word Automaton). Let w Σ and A(w) be the minimal deterministic finite automaton accepting {w}. Then, A(w) has |w| + 2 states. In combination with Lemma 5, we obtain the following. Corollary 14. Let w Σ . Then, the NFA Subseq(A(w)) has |w| + 1 states. Let us move on to questions that are more directly related to our discussions on diversity in synchronization. The next algorithmic result is interesting, as we prove intractability of the corresponding decision problem in Theorem 19 below. Theorem 15. Let A = (Q, Σ, δ, q0, F) be a DFA. Given a word w Σ+, one can determine in O(2|Q| |w| (|A| + log |w|)) time whether w has a subsequence that is synchronizing for A. If yes, in time O(2|Q| |w|2 (|A|+log |w|)), or alternatively, in time O(22|Q| 2|A| |w| log(|w|)), one can even construct a subsequence-minimal synchronizing word for A that is a subsequence of w. Proof. Let Subseq(A(w)) be the NFA of Corollary 14 with |w|+1 states accepting all subsequences of w. Let Sync(A) be the automaton accepting all words that are synchronizing for A. By Lemma 8, this DFA has O(2|Q|) states and can be constructed in time O(2|Q||A|). Then, w has some subsequence that is synchronizing for A if and only if L(Subseq(A(w))) L(Sync(A)) = , a condition that can be verified in time O(2|Q||w|(|A| + log |w|)) by first constructing a product automaton (here, an NFA), and then by performing a reachability test. In the same time bound, we can find some u L(Subseq(A(w))) L(Sync(A)) (if it exists). For the last part, suppose that the intersection above is non-empty. Then, w also contains a subsequence-minimal synchronizing word for A. Using Lemma 7, we can construct an automaton Min Sync(A) that accepts the language of all synchronizing words of A that do not contain any subsequence that is also synchronizing for A. This construction takes time O(22|Q| |Sync(A)|) = O(22|Q| 2|A|). Observe that Min Sync(A) has at most O(22|Q| 2|Q|) states. Hence, it is enough to output any word in the language L(Min Sync(A)) L(Subseq(A(w))). Since Min Sync(A) has O(22|Q| 2|Q|) states and A(w) has |w| + 1 states, we have that one can find a word in the intersection of the languages accepted by these automata in time O(22|Q| 2|Q| |w| log(|w|)). Alternatively, we can obtain an algorithm running in time O(2|Q| |w|2 (|A| + log |w|)) as follows. Above, we described how to test whether L(Subseq(A(w))) L(Sync(A)) is non-empty. If the intersection is empty, then w has no subsequence that is synchronizing for A. In the other case, such a subsequence exists. Let w i = w[1..i 1]w[i + 1..|w|]. If L(Subseq(A(w i))) L(Sync(A)) = for every i [|w|], then we know that w is a subsequenceminimal synchronizing word for A. Otherwise, if this intersection is non-empty for some i, we know that w i contains a subsequence-minimal synchronizing word for A. We then update w to w i, and repeat the process described in this paragraph. The algorithm runs in time O(2|Q| |w|2 (|A| + log |w|)), since we need to delete at most |w| letters, and at each deletion, one needs O(2|Q| |w| (|A|+log |w|)) steps to determine if L(Subseq(A(w i))) L(Sync(A)) = . Next, we deal with the problem of finding a sufficiently diverse set W of subsequence-minimal synchronizing words for an automaton A that satisfy an additional constraint. More specifically, we require that each word in W belongs to the language of an automaton B given at the input. In this setting, A may be regarded as the specification of a system (say a robot) that interacts with an environment. Here, B models the set of all sequences of actions that are legal in the environment. The requirement W L(B) ensures that the synchronizing words under consideration correspond to sequences of actions that are legal in the environment. Note that it makes sense to assume that A is fixed (say, a robot of a certain model), and that the environment may vary (e.g., the environment where the robot will be deployed). The next theorem analyzes the computational complexity of this problem parameterized by the diversity parameters r and k. As A is assumed to be fixed, in the statement of the theorem we hide the dependencies on the DFA A in the function f A. Theorem 16. Let A = (Q, Σ, δ) be a DFA and B = (Q , Σ, δ , Q 0, F ) be an NFA. One can determine in time O(f A(r, k) |Q |r log(|Q |)) if there is a set W L(B) with r strings such that each word in W is subsequence-minimal synchronizing for A and Min Div(W) k. Proof. By combining Corollary 9 with Lemma 12, we can construct a DFA A accepting the language of all compound words u1 ur (Σ { }) r such that for each i [r], ui is a subsequence-minimal synchronizing word for A, and Min Div({u1, . . . , ur}) k. The DFA A has 2r2 2O(k log |Σ|) (2|Q|)r many states and can be constructed in time 2r2 2O(k log |Σ|) (2|Q| |Σ| |Q|)r. Conversely, again by an (r + 1)-fold product automaton construction, also using Lemma 1 and Corollary 2, an NFA B with (2|Q |)r + 1 many states can be constructed that accepts the language {u1 u2 ur : i [r](ui L(B))} . Checking if the product automaton C of A and B accepts any compound words solves the proposed problem. This final check takes time linear in the size of C, which is O 2r2 (|Q|+2O(k log |Σ|)) |Q |r log(|Q |) . The previous result can be viewed as a diversity result concerning synchronization under regular constraints, introduced in (Fernau et al. 2019). This variation of the classical synchronization theme comes with a constraint automaton B; with L(B) = Σ , we get back to the classical theme. Furthermore, as a direct consequence of Theorem 16 and Corollary 14 in combination with Lemma 5, we have that the problem of finding a set of sufficiently diverse subsequences of a word w that are subsequence-minimal synchronizing words for A can be solved by an algorithm with an FPT dependency on the parameters A (i.e., |Q| and |Σ|) and k and an XP dependency on the parameter r. Corollary 17. Let A = (Q, Σ, δ) be a DFA and w be a word in Σ . One can determine in time O(f A(r, k) |w|r log(|w|)) whether there is a set W = {w1, . . . , wr} of subsequences of w such that each word in W is subsequence-minimal synchronizing for A and Min Div(W) k. 7 Hardness Results Below we show that the very problem of determining whether a given word is subsequence-minimal synchronizing for a given DFA A is co NP-hard. Definition 18 (MIN-SUBSEQUENCE-SW). Given: DFA A = (Q, Σ, δ) and w Σ synchronizing A. Question: Is w a minimal synchronizing word with respect to the subsequence order? Theorem 19. MIN-SUBSEQUENCE-SW is co NPcomplete, even for DFAs over a binary input alphabet. This hardness result (and even more the hardness result for the counting class #P, our third main result of this section below in Theorem 24) explains why we have to develop exponential-time algorithms for the suggested diversity problems. We prove the hardness by a reduction from HITTING SET (Karp 1972) to the complementary problem of MIN-SUBSEQUENCE-SW which asks for the existence of a proper synchronizing subsequence of w. Recall that above, in Theorem 15 we proved that MINSUBSEQUENCE-SW, parameterized by the number of states of the input DFA, belongs to FPT. The following result explains also why the problems that we consider are computationally hard ones. Note that in the classical setting, length-minimal synchronizing words (if existent at all) are of polynomial length only (Volkov 2008). Requiring subsequence-minimality instead of lengthminimality changes the picture drastically: with this property, some synchronizing words can be exponentially long. Proposition 20. Some subsequence-minimal synchronizing words can be of exponential length, even for DFAs with a ternary input alphabet. For binary input alphabets, we do not have such an example, giving an open question. For unary alphabets, subsequence-minimality equals length-minimality: lengths of shortest synchronizing words are polynomially bounded. Next, we define two further combinatorial questions, which are in fact the central problems of our study. Above, we showed some algorithmic results that can be viewed as exponential-time algorithms for these problems. The fact that these algorithms exceed polynomial time is (with hindsight) justified by the hardness results proved next. Definition 21 (DIVERSITY-SYNC). Given: DFA A = (Q, Σ, δ) and k N, encoded in binary. Question: Is there a set W = {w1, w2, . . . , wr} of subsequence-minimal synchronizing words for A such that P 1 i