We characterize a class of constraint automata that gives constrained problems in NP, which encompasses all known constrained synchronization problems in NP so far. We call these automata polycyclic automata. The corresponding language class of polycyclic languages is introduced. We show various characterizations and closure properties for this new language class. We then give a criterion for NP-completeness and a criterion for polynomial time solvability for polycyclic constraint languages.
A deterministic semi-automaton is synchronizing if it admits a reset word, i.e.,
a word which leads to some definite state, regardless of the starting state. This
notion has a wide range of applications, from software testing, circuit synthesis,
communication engineering and the like, see [
Our contribution: Here, we generalize a theorem from [
By N “ t0, 1, 2, . . .u we denote the natural numbers, including zero.
Throughout the paper, we consider deterministic finite automata (DFAs). Recall that
a DFA A is a tuple A “ pΣ, Q, δ, q0, F q, where the alphabet Σ is a finite set
of input symbols, Q is the finite state set, with start state q0 P Q, and
final state set F Ď Q. The transition function δ : Q ˆ Σ Ñ Q extends to
words from Σ˚ in the usual way. The function δ can be further extended to
sets of states in the following way. For every set S Ď Q with S ‰ H and
w P Σ˚, we set δpS, wq :“ t δpq, wq | q P S u. We call A complete if δ is
defined for every pq, aq P Q ˆ Σ; if δ is undefined for some pq, aq, the
automaton A is called partial. If |Σ| “ 1, we call A a unary automaton. The set
LpAq “ t w P Σ˚ | δpq0, wq P F u denotes the language accepted by A. A
semi-automaton is a finite automaton without a specified start state and with
no specified set of final states. The properties of being deterministic, partial,
and complete of semi-automata are defined as for DFA. When the context is
clear, we call both deterministic finite automata and semi-automata simply
automata. We call a deterministic complete semi-automaton a DCSA and a
partial deterministic finite automaton a PDFA for short. If we want to add an
explicit initial state r and an explicit set of final states S to a DCSA A or
change them in a DFA A, we use the notation Ar,S . A nondeterministic finite
automaton (NFA) A is a tuple A “ pΣ, Q, δ, s0, F q where δ Ď Q ˆ Σ ˆ Q
is an arbitrary relation. Hence, they generalize deterministic automata. With
a nondeterministic automaton A we also associate the set of accepted words
LpAq “ tw P Σ˚ | w labels a path from s0 to some state in F u. We refer to [
The following obvious remark will be used frequently without further mentioning. Lemma 1. Let A “ pΣ, Q, δq be a DCSA and w P Σ˚ be a synchronizing word for A. Then for every u, v P Σ˚, the word uwv is also synchronizing for A.
For a fixed PDFA B “ pΣ, P, µ, p 0, F q, we define the constrained synchronization problem:
Input: Deterministic complete semi-automaton A “ pΣ, Q, δq.
Question: Is there a synchronizing word w P Σ˚ for A with w P LpBq?
The automaton B will be called the constraint automaton. If an automaton
A is a yes-instance of LpBq-Constr-Sync we call A synchronizing with
respect to B. Occasionally, we do not specify B and rather talk about
L-ConstrSync. We assume the reader to have some basic knowledge in computational
complexity theory and formal language theory, as contained, e.g., in [
Lemma 2. For any automaton B “ pΣ, P, µ, p 0, F q and any p P P , we have LpBp,tpuq “ C˚ for some regular prefix-free set C Ď Σ˚.
We will also need the following combinatorial lemma from [
Lemma 3. [
In [
Input: DCSA A “ pΣ, Q, δq and two subsets S, T Ď Q.
Question: Is there a word w P Σ˚ such that δpS, wq Ď T ? We will only use the following variant, which has the same complexity.
Decision Problem 3: DisjointSetTransporter Input: DCSA A “ pΣ, Q, δq and two subsets S, T Ď Q with S X T “ H.
Question: Is there a word w P Σ˚ such that δpS, wq Ď T ? Proposition 1. The problems SetTransporter and DisjointSetTransporter are equivalent under polynomial time many-one reductions.
Proposition 2. For unary DCSAs problem SetTransporter is NP-complete.
In [
Theorem 1. Let B “ pΣ, P, µ, p 0, F q be a PDFA. Then, LpBq-Constr-Sync P NP if there is a σ P Σ such that for all states p P P , if LpBp,tpuq is infinite, then LpBp,tpuq Ď tσu˚. 3
First, in Section 3.1, we introduce polycyclic automata and generalize Theorem 1, thus widening the class for which the problem is contained in NP. Then, in Section 3.2, we take a closer look at polycyclic automata. We determine their form, show that they admit definitions by partial and by nondeterministic automata and prove some closure properties. In Section 3.3 we state a general criterion that gives a polynomial time solvable problem. Then, in Section 3.4, we give a sufficient criterion for constraint languages that give NP-complete problems, which could be used to construct polycyclic constraint languages that give NP-complete problems. 3.1
The main result of this section is Theorem 2. But first, let us introduce the class of polycyclic partial automata.
polycyclic, if for all states p P P we have LpBp,tpuq Ď tupu˚ for some up P Σ˚.
The results from Section 3.2 will give some justification why we call these automata polycyclic. In Definition 1, languages that are given by automata with a single final state, which equals the start state, occur. Our first Lemma 4 determines the form of these languages, under the restriction in question, more precisely. Note that in any PDFA B “ pΣ, P, µ, p 0, F q we have either that LpBp,tpuq is infinite or LpBp,tpuq “ tεu.
Lemma 4. Let B “ pΣ, P, µ, p 0, F q be a PDFA. Suppose p P P such that LpBp,tpuq Ď tupu˚ for some up P Σ˚. Then LpBp,tpuq “ tupnu˚ for some n ě 1.
Theorem 2. Let B “ pΣ, P, µ, p 0, F q be a polycyclic partial automaton. Then LpBq-Constr-Sync P NP.
Proof. By Lemma 4, we can assume LpBp,tpuq “ tupu˚ for some up ‰ ε for each p P P such that LpBp,tpuq ‰ tεu. Let U “ tup | LpBp,tpuq “ tupu˚ with up ‰ ε for some p P P u be all such words. Set m “ |P |. Every word of length greater than m´1 must traverse some cycle. Therefore, any word w P LpBq can be partitioned into at most 2m ´ 1 substrings w “ upn11 v1 ¨ ¨ ¨ upnmm´´11 vm´1upnmm for numbers n1, . . . , nm ě 0, p1, . . . , pm P P and words v1, . . . , vm´1. Note that |vi| ď m ´ 1 for all i ď m ´ 1. Let A “ pΣ, Q, δq be a yes-instance of LpBq-Constr-Sync. Let w P LpBq be a synchronizing word for A partitioned as mentioned above. Claim 1: If for some i ď m we have ni ě 2|Q|, then we can replace it by some n1i ă 2|Q|, yielding a word w1 P LpBq that synchronizes A. This could be seen by considering the non-empty subsets
δpQ, upn11 v1 ¨ ¨ ¨ upnjj´´11 vj´1upkj q for k “ 0, 1, . . . , ni. If ni ě 2|Q|, then some such subsets appears at least twice, but then we can delete the power of upi between those appearances.
We will now show that we can decide whether A is synchronizing with respect to B in polynomial time using nondeterminism despite the fact that an actual synchronizing word might be exponentially large. This problem is circumvented by some preprocessing based on modulo arithmetic, and by using a more compact representation for a synchronizing word. We will assume we have some numbering of the states, hence the pi are numbers. Then, instead of the above form, we will represent a synchronizing word in the form wcode “ 1p1 # binpn1qv11p2 # binpn2qv2 . . . vm´11pm # binpnmq, where # is some new symbol that works as a separator, and similarly t0, 1u X Σ “ H are new symbols to write down the binary number, or the unary presentation of pi, indicating which word upi is to be repeated. As binpniq ď |Q| by the above claim and m is fixed by the problem specification, the length of wcode is polynomially bounded, and we use nondeterminism to guess such a code for a synchronizing word.
Claim 2: For each q P Q and u P Σ˚, one can compute in polynomial time numbers ℓpqq, τ pqq ď |Q| such that, given some number x in binary, based on ℓpqq, τ pqq, one can compute in polynomial time a number y ď |Q| such that δpq, uxq “ δpq, uyq.
Proof (Proof of Claim 2 of Theorem 1). For each state q P Q and u P Σ˚, we calculate its u-orbit Orbupqq, that is, the set Orbupqq “ tq, δpq, uq, δpq, u2q, . . . , δpq, uτ q, δpq, uτ`1q, . . . , δpq, uτ`ℓ´1qu such that all states in Orbupqq are distinct but δpq, uτ`ℓq “ δpq, uτ q. Let τ pqq :“ τ and ℓpqq :“ ℓ be the lengths of the tail and the cycle, respectively; these are nonnegative integers that do not exceed |Q|. Observe that Orbupqq includes the cycle tδpq, uτ q, . . . , δpq, uτ`ℓ´1qu. We can use this information to calculate δpq, uxq, given a nonnegative integer x and a state q P Q, as follows: (a) If x ď τ pqq, we can find δpq, uxq P Orbσpqq. (b) If x ą τ pqq, then δpq, uxq lies on the cycle. Compute y :“ τ pqq`px´τ pqqq pmod ℓpqqq. Clearly, δpq, uxq “ δpq, uyq P Orbσpqq. The crucial observation is that this computation can be done in time polynomial in |Q| and in | binpxq|. As a consequence, given S Ď Q and x ě 0 (in binary), we can compute δpS, uxq in polynomial time.
The NP-machine guesses wcode part-by-part, keeping track of the set S of active states of A and of the current state p of B. Initially, S “ Q and p “ p0. For i P t1, . . . , mu, when guessing the number ni in binary, by Claim 1 we guess logpniq ď n many bits. By Claim 2, we can update S :“ δpS, upnii q and p :“ µ pp, upnii q in polynomial time. After guessing vi, we can simply update S :“ δpS, viq and p :“ µ pp, viq by simulating this input, as |vi| ď m “ |P |, which is a constant in our setting. Finally, check if |S| “ 1 and if p P F . \[
Comparing Theorem 2 with Theorem 1 shows that our generalization allows entire words as a restriction instead of powers of a single letter for languages of the form LpBp,tpuq, and these words could be different for each state.
Properties of Polycyclic Automata Here, we look closer at polycyclic automata. We find that every strongly connected component of a polycyclic PDFA essentially consists of a single cycle, i.e, for each strongly connected component S Ď P and p P S we have |tµ pp, xq | x P Σ, µ pp, xq is defined u X S| ď 1. Hence, these automata admit a notable simple structure. We then introduce the class of polycyclic languages. In Proposition 4 we show that these languages could be characterized with accepting nondeterministic automata. This result yields closure under union. Proposition 3. Let B “ pΣ, P, µ, p 0, F q be a PDFA. Then every strongly connected component of B is a single cycle if and only if B is polycyclic.
Definition 2. A language L Ď Σ˚ is called polycyclic, if there exists a polycylic PDFA accepting it.
Hence, we have the result that the constrained synchronization problem is in NP if the constraint language is polycyclic. By our results, if L gives a constrained synchronization problem outside of NP, then L could not be polycyclic. But we also state a simpler necessary criterion.
Lemma 5. Let L Ď Σ˚ and let a, b P Σ be distinct letters. If we find u P Σ˚ and a, b P Σ` such that upa ` bq˚ Ď L, then L is not polycyclic.
By adding a trap state, we can convert every PDFA into a complete DFA accepting the same language. But the resulting complete DFA is not polycyclic anymore for |Σ| ą 1, as the trap state has a cycle for every letter. The language L “ ab˚ is polycyclic, but its complement bpa ` bq˚ Y apa ` bq˚apa ` bq˚ is not polycyclic by Lemma 5. Hence, the polycyclic languages are not closed under complement, which implies that we could not have a structural characterization in terms of complete DFA without reference to the set of final states. However, we can use nondeterministic automata in the definition of polycyclic languages. We need the next lemma to prove this claim.
Lemma 6. Let B “ pΣ, P, µ, p 0, F q be a PDFA such that for some state p P P we have LpBp,tpuq Ď v˚ Y w˚. Then LpBp,tpuq Ď u˚ for some word u P Σ˚.
With Lemma 6 we can prove the next characterization by NFAs. Proposition 4. A language L Ď Σ˚ is polycyclic if and only if it is accepted by a nondeterministic automaton A “ pΣ, Q, δ, s0, F q such that for all states p P Q we have LpAp,tpuq Ď tupu˚ for some up P Σ˚.
A useful property, which will be used in Section 3.4 for constructing examples that yield NP-complete problems, is that the class of polycyclic languages is closed under concatenation. We need the next lemma to prove this claim, which gives a certain normal form. Lemma 7. Let L Ď Σ˚ be a polycyclic language. Then, there exists an accepting polycyclic PDFA B “ pΣ, P, µ, p 0, F q such that p0 is not contained in any cycle, i.e., LpBp0,tp0uq “ tεu.
Intuitively, for an automaton B “ pΣ, P, µ, p 0, F q that has the form as stated in Lemma 7, we can compute its concatenation L ¨ LpBq with another regular language L Ď Σ˚ by identifying p0 with every final state of an automaton for L. Proposition 5. If U, V Ď Σ˚ are polycyclic, then U ¨ V is polycyclic.
Proposition 6. The polycyclic languages are closed under union and quotients.
Without proof, we note that polycyclic automata are a special case of
solvable automata as introduced in [
Polynomial Time Solvable Cases
a sufficient criterion for a polycyclic constraint automaton that gives constrained synchronization problems that are solvable in polynomial time.
Please see Figure 1 for an example constraint automaton whose constrained synchronization problem is in P according to Proposition 7.
Proposition 7. Let B “ pΣ, P, µ, p 0, F q be a polycyclic PDFA. If for any
reachable p P P with LpBp,tpuq ‰ tεu we have LpBp0,tpuq Ď SuffpLpBp,tpuqq, then the
problem LpBq-Constr-Sync is solvable in polynomial time.
1 Solvable automata according to Rystsov [
b Fig. 1. An example constraint automaton with LpBq-Constr-Sync P P.
a a b a b Proof. By Lemma 4, we can assume LpBp,tpuq “ tupu˚ for some up ‰ ε for each p P P such that LpBp,tpuq ‰ tεu. Let U “ tup | LpBp,tpuq “ tupu˚ with up ‰ ε for some p P P u be all such words. Set m “ |P |. Every word of length greater than m´1 must traverse some cycle. Therefore, any word w P LpBq can be partitioned into at most 2m ´ 1 substrings w “ upn11 v1 ¨ ¨ ¨ upnmm´´11 vm´1upnmm for numbers n1, . . . , nm ě 0, p1, . . . , pm P P and words v1, . . . , vm´1. Note that |vi| ď m ´ 1 for all i ď m ´ 1. Let A “ pΣ, Q, δq be a yes-instance of LpBq-Constr-Sync. Let w P LpBq be a synchronizing word for A partitioned as mentioned above. We show that by our assumptions we could choose the numbers n1, . . . , nm to be strictly smaller than |Q|.
Claim 1: If for some i ď m we have ni ě |Q|, then we can replace it by n1i “ |Q| ´ 1, yielding a word w1 P LpBq that synchronizes A.
Proof (Proof of Claim 1 of Proposition 7). Let j P t1, . . . , mu be arbitrary with nj ě |Q| and upj ‰ ε (otherwise we have nothing to prove). Set u “ upn11 v1upn22 v2 ¨ ¨ ¨ upnjj´´11 vj´1 and S “ δpQ, uq. By choice of the decomposition of w, if nj ą 0, then µ pp0, uq “ pj and LpBpj,tpjuq “ tupj u˚. Write p “ pj. As by assumption u appears as a suffix of some word from LpBp,tpuq, we have ulp “ vu for some v P Σ˚ and l ě 0. Hence, for each k P N0 we have δpS, ulpkq Ď S as every word that has u as a suffix maps any state to a state in S. Let us assume l “ 1 in the following argument, as this is a fixed parameter of LpBq-Constr-Sync only depending on u. Hence, the conclusion would be the same if we replace up by ulp in the following arguments.
First, we show δpS, u|pS|q “ δpS, u|pS|´1q. For q P S we have δpq, u|pS|q “ δpδpq, upq, u|pS|´1q and as δpq, upq P S this gives δpS, u|pS|q Ď δpS, u|pS|´1q. Now let us show the other inclusion δpS, u|pS|´1q Ď δpS, u|pS|q. Let q P S. By the pigeonhole principle
δpq, u|pS|q P tq, δpq, upq, . . . , δpq, u|pS|´1qu.
Hence δpq, u|pS|q equals δpq, upkq for some 0 ď k ă |S|. Choose a, b ě 0 such that |S| “ ap|S| ´ kq ` b with 0 ď b ă |S| ´ k. Note that δpq, upk`l`ap|S|´kqq “ δpq, upk`lq for each l ě 0 because δpq, upk`|S|´kq “ δpq, u|pS|q “ δpq, upkq. Set q1 “ δpδpq, u|pS|´1q, u|pS|´k´bq. By assumption q1 P S. Then δpq1, u|pS|q “ δpq, u|pS|´1`|S|´k´b`|S|q “ δpq, u|pS|´1`|S|´k`ap|S|´kqq “ δpq, u|pS|´1q.
So δpq, u|pS|´1q P δpS, u|pS|q. Hence, regarding our original problem, if nj ě |Q| ě |S|, we have δpQ, uupnjj q “ δpQ, uu|pQj |´1q, as inductively δpQ, uupnjj q “ δpS, upnjj q “ δpS, u|pSj|´1q “ δpS, u|pQj |´1q “ δpQ, uu|pQj |´1q.
So, to find out if we have any synchronizing word in LpBq, we only have to test the finitely many words
upn11 v1 ¨ ¨ ¨ upnmm´´11 vm´1upnmm for n1, . . . , nm´1, nm P t0, 1, . . . , |Q| ´ 1u, up1 , . . . , upm´1 , upm P Up and words v1, . . . , vm´1 of length at most m. As m “ |P | and Up is fixed, we have to test Op|Q|mq many words. For each word w “ upn11 v1 ¨ ¨ ¨ upnmm´´11 vm´1upnmm , we have to read in this word starting from any state in Q and check if a unique state results, i.e., check if δpq, wq “ δpq1, wq for q, q1 P Q. All these operations could be performed in polynomial time with parameter |Q|. [\ 3.4
In [
Prefpv˚q X U “ H.
Then L-Constr-Sync is NP-hard.
Proof. Note that u R Factpv˚q implies u ‰ ε, v R FactpU q implies v ‰ ε and Prefpv˚q X U “ H with U ‰ H implies U X Σ` ‰ H. We show NP-hardness by reduction from DisjointSetTransporter for unary automata, which is NP-complete by Proposition 1 and Proposition 2. Let pA, S, T q be an instance of DisjointSetTransporter with unary semi-automaton A “ ptcu, Q, δq. Write v|u| “ x1 ¨ ¨ ¨ xn with xi P Σ for i P t1, . . . , nu. We construct a new semi-automaton A1 “ pΣ, Q1, δ1q with Q1 “ Q Y Q1 Y . . . Y Qn´1 Y ttu, where Qi “ tqi | q P Qu are disjoint copies of Q and t is a new state that will work as a trap state in A1. Assume ϕi : Q Ñ Qi for i P t1, . . . , n ´ 1u are bijections with ϕipqq “ qi. Also, to simplify the formulas, set Q “ Q0 and ϕ0 : Q Ñ Q the identity map. Choose some sˆ P S. Then, for r P Q1 and x P Σ we define $ ϕi`1pqq ’’’ δpq, cq ’ δ1pr, xq “ &’’ sˆ
q ’’’ t ’ ’’% t
Di P t0, 1, . . . , n ´ 2u : r P Qi, r “ ϕipqq, x “ xi`1; r P Qn´1, r “ ϕn´1pqq, x “ xn; Di P t0, 1, . . . , n ´ 1u : r P Qi, r “ ϕipqq, q R T Y S, x ‰ xi`1; Di P t0, 1, . . . , n ´ 1u : r P Qi, r “ ϕipqq, q P S, x ‰ xi`1; Di P t0, 1, . . . , n ´ 1u : r P Qi, r “ ϕipqq, q P T, x ‰ xi`1; r “ t. (1) (2) Note that by construction of A1, we have for q P Q Y Q1 Y . . . Y Qn´1 and w P Σ˚ δpq, wq “ t ô Dx, y, z P Σ˚ : w “ xyz, δpq, xq P T, y R Prefpv|u|q and for q, q1 P Q δpq, cq “ q1 in A
ô δ1pq, v|u|q “ q1 in A1 .
So, we have a synchronizing word for A1 from LpBq if and only if we can map the set S into T in A. [\
If u, v P Σ˚ with u R Factpv˚q, by choosing U “ twu with w R Prefpvq Y Σ˚vΣ˚ we get that uv˚w gives an NP-complete problem. Also our result shows that for example aapbaq˚aaa˚a yields an NP-complete problem. 4
We introduced the class of polycyclic automata and showed that for polycyclic constraint automata, the constrained synchronization problem is in NP. For these contraint automata, we have given a sufficient criterion that yields problems in P, and a criterion that yields problems that are NP-complete. However, both criteria do not cover all cases. Hence, there are still polycyclic constraint automata left for which we do not know the exact computational complexity in NP of the constrained synchronization problem. A dichotomy theorem for our class, i.e, that every problem is either NP-complete or in P, would be very interesting. However, much more interesting would be if we could find any candidate NP-intermediate problems. Lastly, we took a closer look at polycyclic automata, determined their form and also gave a characterization in terms of nondeterministic automata. We also introduced polycyclic languages and proved basic closure properties for this class.
Acknowledgement. I thank Prof. Dr. Mikhail V. Volkov for suggesting the problem of constrained synchronization during the workshop ‘Modern Complexity Aspects of Formal Languages’ that took place at Trier University 11.–15. February, 2019. The financial support of this workshop by the DFG-funded project FE560/9-1 is gratefully acknowledged. I also thank the anonymous reviewers for their suggestions which helped in improving the presentation.