=Paper=
{{Paper
|id=Vol-2756/paper19
|storemode=property
|title=On A Class of Constrained Synchronization Problems in NP
|pdfUrl=https://ceur-ws.org/Vol-2756/paper_19.pdf
|volume=Vol-2756
|authors=Stefan Hoffmann
|dblpUrl=https://dblp.org/rec/conf/ictcs/Hoffman20
}}
==On A Class of Constrained Synchronization Problems in NP==
https://ceur-ws.org/Vol-2756/paper_19.pdf
On a Class of Constrained Synchronization
Problems in NP‹
Stefan Hoffmann
Informatikwissenschaften, FB IV, Universität Trier, Universitätsring 15, 54296 Trier,
Germany, hoffmanns@informatik.uni-trier.de
Abstract. 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.
Keywords: finite automata · synchronization · computational complex-
ity · polycyclic automata
1 Introduction
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 [19, 21]. The famous Černý conjec-
ture [3] states that a minimal synchronizing word has at most quadratic length.
We refer to the mentioned survey articles for details. Due to its importance, the
notion of synchronization has undergone a range of generalizations and varia-
tions for other automata models. It was noted in [14] that in some generalizations
only certain paths, or input words, are allowed (namely those for which the input
automaton is defined). In [9] the notion of constrained synchronization was in-
troduced in connection with a reduction procedure for synchronizing automata.
The paper [8] introduced the computational problem of constrained synchro-
nization. In this problem, we search for a synchronizing word coming from some
specific subset of allowed input sequences. For further motivation and applica-
tions we refer to the aforementioned paper [8]. Let us mention that restricting
the solution space by a regular language has also been applied in other areas,
for example to topological sorting [1], solving word equations [4, 5], constraint
programming [15], or shortest path problems [17]. In [8] it was shown that the
‹
Copyright c 2020 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
2 S. Hoffmann
smallest partial constraint automaton for which the problem becomes PSPACE-
complete has two states and a ternary alphabet. Also, the smallest constraint
automaton for which the problem is NP-complete needs three states and a binary
alphabet. A complete classification of the complexity landscape for constraint
automata with two states and a binary or ternary alphabet was given in [8].
In [11] the result for two-state automata was generalized to arbitrary alphabets,
and a complexity classification for special three-state constraint automata over a
binary alphabet was given. As shown in [10], for regular commutative constraint
languages we only find constrained problems that are NP-complete, PSPACE-
complete, or solvable in polynomial time. In all the mentioned work [8, 10, 11],
it was noted that the constraint automata for which the corresponding con-
strained synchronization problem is NP-complete admit a special form, which
we generalize in this work.
Our contribution: Here, we generalize a theorem from [8] to give a wider
class of constrained synchronization problems in NP. As noted in [11], the con-
straint automata that yield problems in NP admit a special form and our class
encompasses all known cases of constrained problems in NP. We also give a
characterization that this class is given precisely by those constraint automata
whose strongly connected components are single cycles. We call automata of this
type polycyclic. Then we introduce the language class of polycyclic languages.
We show that this class is closed under union, quotients, concatenation and also
admits certain robustness properties with respect to different definitions by par-
tial or nondeterministic automata. Lastly, we also give a criterion for our class
that yields constrained synchronization problems that are NP-complete and a
criterion for problems in P.
2 Preliminaries and Definitions
By N “ t0, 1, 2, . . .u we denote the natural numbers, including zero. Through-
out 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 fi-
nal 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 de-
fined for every pq, aq P Q ˆ Σ; if δ is undefined for some pq, aq, the automa-
ton 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 au-
tomata. We call a deterministic complete semi-automaton a DCSA and a par-
tial deterministic finite automaton a PDFA for short. If we want to add an
On a Class of Constrained Synchronization Problems in NP 3
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 [12]
for a more formal treatment. In this work, when we only use the word automaton
without any adjective, we always mean a deterministic automaton. An automa-
ton A is called synchronizing if there exists a word w P Σ ˚ with |δpQ, wq| “ 1.
In this case, we call w a synchronizing word for A. For a word w, we call a state
in δpQ, wq an active state. We call a state q P Q with δpQ, wq “ tqu for some
w P Σ ˚ a synchronizing state. A state from which some final state is reachable
is called co-accessible. For a set S Ď Q, we say S is reachable from Q or Q is
synchronizable to S if there exists a word w P Σ ˚ such that δpQ, wq “ S. We call
an automaton initially connected, if every state is reachable from the start state.
Fact 1 [21] For any DCSA, we can decide if it is synchronizing in polynomial
time Op|Σ||Q|2 q. Additionally, we can compute a synchronizing word of length
at most Op|Q|3 q in time Op|Q|3 ` |Q|2 |Σ|qq.
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, µ, p0 , F q, we define the constrained synchro-
nization problem:
Decision Problem 1: [8] LpBq-Constr-Sync
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 re-
spect to B. Occasionally, we do not specify B and rather talk about L-Constr-
Sync. We assume the reader to have some basic knowledge in computational
complexity theory and formal language theory, as contained, e.g., in [12]. For
instance, we make use of regular expressions to describe languages, or use many-
one polynomial time reductions. We write ε for the empty word, and for w P Σ ˚
we denote by |w| the length of w. For some language L Ď Σ ˚ , we denote by
PrefpLq “ tw | Du P Σ ˚ : wu P Lu, SuffpLq “ tw | Du P Σ ˚ : uw P Lu and
FactpLq “ tw | Du, v P Σ ˚ : uwv P Lu the set of prefixes, suffixes and factors
of words in L. The language L is called prefix-free if for each w P L we have
Prefpwq X L “ twu. If u, w P Σ ˚ , a prefix u P Prefpwq is called a proper prefix
if u ‰ w. For L Ď Σ ˚ and u P Σ ˚ , the language u´1 L “ tw P Σ | uw P Lu is
called a quotient (of L by u). We identify singleton sets with its elements. And
we make use of complexity classes like P, NP, or PSPACE. A trap (or sink) state
in a (semi-)automaton A “ pΣ, Q, δq is a state q P Q such that δpq, xq “ q for
4 S. Hoffmann
each x P Σ. If a synchronizable automaton admits a sink state, then this is the
only state to which we could synchronize every other state, as it could only map
to itself. For an automaton A “ pΣ, Q, δ, q0 , F q, we say that two states q, q 1 P Q
are connected, if one is reachable from the other, i.e., we have a word u P Σ ˚
such that δpq, uq “ q 1 . A subset S Ď Q of states is called strongly connected, if
all pairs from S are connected. A maximal strongly connected subset is called a
strongly connected component. By combining Proposition 3.2 and Proposition 5.1
from [7], we get the next result.
Lemma 2. For any automaton B “ pΣ, P, µ, p0 , F q and any p P P , we have
LpBp,tpu q “ C ˚ for some regular prefix-free set C Ď Σ ˚ .
We will also need the following combinatorial lemma from [20].
Lemma 3. [20] Let u, v P Σ ˚ . If um “ v n and m ě 1, then u and v are powers
of a common word.
In [2,13] the decision problem SetTransporter was introduced. In general
it is PSPACE-complete.
Decision Problem 2: [2, 13] SetTransporter
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 DisjointSetTrans-
porter are equivalent under polynomial time many-one reductions.
We will use Problem 3 for unary input DCSAs.
Proposition 2. For unary DCSAs problem SetTransporter is NP-complete.
In [8], with Theorem 1, a sufficient criterion was given when the constrained
synchronization problem is in NP.
Theorem 1. Let B “ pΣ, P, µ, p0 , 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,tpu q is infinite, then
LpBp,tpu q Ď tσu˚ .
3 Results
First, in Section 3.1, we introduce polycyclic automata and generalize Theo-
rem 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
On a Class of Constrained Synchronization Problems in NP 5
form, show that they admit definitions by partial and by nondeterministic au-
tomata 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 A Sufficient Criterion for Containment in NP
The main result of this section is Theorem 2. But first, let us introduce the class
of polycyclic partial automata.
Definition 1 (polycyclic PDFA). A PDFA B “ pΣ, P, µ, p0 , F q is called
polycyclic, if for all states p P P we have LpBp,tpu q Ď tup u˚ 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 deter-
mines the form of these languages, under the restriction in question, more pre-
cisely. Note that in any PDFA B “ pΣ, P, µ, p0 , F q we have either that LpBp,tpu q
is infinite or LpBp,tpu q “ tεu.
Lemma 4. Let B “ pΣ, P, µ, p0 , F q be a PDFA. Suppose p P P such that
LpBp,tpu q Ď tup u˚ for some up P Σ ˚ . Then LpBp,tpu q “ tunp u˚ for some n ě 1.
Now, we are ready to state the main result of this section.
Theorem 2. Let B “ pΣ, P, µ, p0 , F q be a polycyclic partial automaton. Then
LpBq-Constr-Sync P NP.
Proof. By Lemma 4, we can assume LpBp,tpu q “ tup u˚ for some up ‰ ε for each
p P P such that LpBp,tpu q ‰ tεu. Let U “ tup | LpBp,tpu q “ tup u˚ 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 parti-
nm´1
tioned into at most 2m ´ 1 substrings w “ unp11 v1 ¨ ¨ ¨ upm´1 vm´1 unpm
m
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, unp11 v1 ¨ ¨ ¨ unpj´1
j´1
vj´1 ukpj 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.
6 S. Hoffmann
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 us-
ing a more compact representation for a synchronizing word. We will assume
we have some numbering of the states, hence the pi are numbers. Then, in-
stead of the above form, we will represent a synchronizing word in the form
wcode “ 1p1 # binpn1 qv1 1p2 # binpn2 qv2 . . . vm´1 1pm # binpnm q, 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 , in-
dicating which word upi is to be repeated. As binpni q ď |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, ux q “ δpq, uy q.
Proof (Proof of Claim 2 of Theorem 1). For each state q P Q and u P Σ ˚ ,
we calculate its u-orbit Orbu pqq, that is, the set
Orbu pqq “ tq, δpq, uq, δpq, u2 q, . . . , δpq, uτ q, δpq, uτ `1 q, . . . , δpq, uτ `ℓ´1 qu
such that all states in Orbu pqq are distinct but δpq, uτ `ℓ q “ δpq, uτ q. Let
τ pqq :“ τ and ℓpqq :“ ℓ be the lengths of the tail and the cycle, respec-
tively; these are nonnegative integers that do not exceed |Q|. Observe
that Orbu pqq includes the cycle tδpq, uτ q, . . . , δpq, uτ `ℓ´1 qu. We can use
this information to calculate δpq, ux q, given a nonnegative integer x and a
state q P Q, as follows: (a) If x ď τ pqq, we can find δpq, ux q P Orbσ pqq. (b)
If x ą τ pqq, then δpq, ux q lies on the cycle. Compute y :“ τ pqq`px´τ pqqq
pmod ℓpqqq. Clearly, δpq, ux q “ δpq, uy q P Orbσ pqq. The crucial observa-
tion 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, ux q 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 logpni q ď n many bits. By Claim 2, we can update S :“ δpS, unpii q and
p :“ µpp, unpii q in polynomial time. After guessing vi , we can simply update
S :“ δpS, vi q and p :“ µpp, vi q 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,tpu q, and these words could be different for each state.
On a Class of Constrained Synchronization Problems in NP 7
3.2 Properties of Polycyclic Automata
Here, we look closer at polycyclic automata. We find that every strongly con-
nected component of a polycyclic PDFA essentially consists of a single cy-
cle, 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 ac-
cepting nondeterministic automata. This result yields closure under union.
Proposition 3. Let B “ pΣ, P, µ, p0 , F q be a PDFA. Then every strongly con-
nected component of B is a single cycle if and only if B is polycyclic.
We transfer our definition from automata to languages.
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, µ, p0 , F q be a PDFA such that for some state p P P
we have LpBp,tpu q Ď v ˚ Y w˚ . Then LpBp,tpu q Ď 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,tpu q Ď tup u˚ 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.
8 S. Hoffmann
Lemma 7. Let L Ď Σ ˚ be a polycyclic language. Then, there exists an accepting
polycyclic PDFA B “ pΣ, P, µ, p0 , F q such that p0 is not contained in any cycle,
i.e., LpBp0 ,tp0 u q “ tεu.
Intuitively, for an automaton B “ pΣ, P, µ, p0 , 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.
We also have further closure properties.
Proposition 6. The polycyclic languages are closed under union and quotients.
Without proof, we note that polycyclic automata are a special case of solv-
able automata as introduced in [18]. Solvable automata are constructed out of
commutative automata, and here polycyclic automata are constructed out of
cycles in the same manner1 . Without getting to technical, let us note that in ab-
stract algebra and the theory of groups, a polycyclic group is a group constructed
out of cyclic groups in the same manner as a solvable group is constructed out
of commutative groups [16]. Hence, the naming supports the analogy to group
theory quite well. Also, let us note that polycyclic automata have cycle rank [6]
at most one, hence they have star height at most one. But they are properly
contained in the languages of star height one, as shown for example by pa ` bq˚ .
3.3 Polynomial Time Solvable Cases
Here, with Proposition 7, we state
a sufficient criterion for a poly-
cyclic constraint automaton that gives b
constrained synchronization problems
that are solvable in polynomial time. b
a
a
a
b
Please see Figure 1 for an exam- start
ple constraint automaton whose con-
strained synchronization problem is in Fig. 1. An example constraint automaton
with LpBq-Constr-Sync P P.
P according to Proposition 7.
Proposition 7. Let B “ pΣ, P, µ, p0 , F q be a polycyclic PDFA. If for any reach-
able p P P with LpBp,tpu q ‰ tεu we have LpBp0 ,tpu q Ď SuffpLpBp,tpu qq, then the
problem LpBq-Constr-Sync is solvable in polynomial time.
1
Solvable automata according to Rystsov [18] always have a trap state and are com-
plete. If our partial automata are not complete, then we can make them complete
by adding a trap state and the analogy is meant in this ways, where special atten-
tion has to be paid to the trap state as it is in general not a single cycle. If the
polycyclic automaton happens to be complete, Rystsov’s [18] definition has to be
altered slightly by not demanding the lowest automaton in a composition chain to
be a single state complete automaton.
On a Class of Constrained Synchronization Problems in NP 9
Proof. By Lemma 4, we can assume LpBp,tpu q “ tup u˚ for some up ‰ ε for each
p P P such that LpBp,tpu q ‰ tεu. Let U “ tup | LpBp,tpu q “ tup u˚ 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 parti-
nm´1
tioned into at most 2m ´ 1 substrings w “ unp11 v1 ¨ ¨ ¨ upm´1 vm´1 unpm
m
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 arbi-
trary with nj ě |Q| and upj ‰ ε (otherwise we have nothing to prove).
nj´1
Set u “ unp11 v1 unp22 v2 ¨ ¨ ¨ upj´1 vj´1 and S “ δpQ, uq. By choice of the de-
composition of w, if nj ą 0, then µpp0 , uq “ pj and LpBpj ,tpj u q “ tupj u˚ .
Write p “ pj . As by assumption u appears as a suffix of some word from
LpBp,tpu q, we have ulp “ vu for some v P Σ ˚ and l ě 0. Hence, for each
k P N0 we have δpS, ulk p q Ď 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.
|S| |S|´1 |S|
First, we show δpS, up q “ δpS, up q. For q P S we have δpq, up q “
|S|´1 |S| |S|´1
δpδpq, up q, up q and as δpq, up q P S this gives δpS, up q Ď δpS, up q.
|S|´1 |S|
Now let us show the other inclusion δpS, up q Ď δpS, up q. Let q P S.
By the pigeonhole principle
δpq, u|S| |S|´1
p q P tq, δpq, up q, . . . , δpq, up qu.
|S|
Hence δpq, up q equals δpq, ukp q for some 0 ď k ă |S|. Choose a, b ě
0 such that |S| “ ap|S| ´ kq ` b with 0 ď b ă |S| ´ k. Note that
k`l`ap|S|´kq k`|S|´k
δpq, up q “ δpq, uk`l
p q for each l ě 0 because δpq, up q“
|S| |S|´1 |S|´k´b
δpq, up q “ δpq, ukp q. Set q 1 “ δpδpq, up q, up q. By assumption
q 1 P S. Then
δpq 1 , u|S| |S|´1`|S|´k´b`|S|
p q “ δpq, up q
“ δpq, u|S|´1`|S|´k`ap|S|´kq
p q
“ δpq, u|S|´1
p q.
|S|´1 |S|
So δpq, up q P δpS, up q. Hence, regarding our original problem, if
n |Q|´1
nj ě |Q| ě |S|, we have δpQ, uupjj q “ δpQ, uupj q, as inductively
n n |S|´1 |Q|´1 |Q|´1
δpQ, uupjj q “ δpS, upjj q “ δpS, upj q “ δpS, upj q “ δpQ, uupj q.
10 S. Hoffmann
So, to find out if we have any synchronizing word in LpBq, we only have to
test the finitely many words
unp11 v1 ¨ ¨ ¨ upnm´1
m´1
vm´1 unpm
m
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
nm´1
Op|Q|m q many words. For each word w “ unp11 v1 ¨ ¨ ¨ upm´1 vm´1 unpm
m
, 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 “ δpq 1 , wq for q, q 1 P Q. All these operations could
be performed in polynomial time with parameter |Q|. [ \
3.4 NP-complete Cases
In [8] it was shown that for the constraint language L “ ba˚ b and for the lan-
guages Li “ pb˚ aqi with i ě 2 the corresponding constrained synchronization
problems are NP-complete. All NP-complete problems with a 3-state constraint
automaton and a binary alphabet where determined in [11]. Here, with Propo-
sition 8, we state a general scheme, involving the concatenation operator, to
construct NP-hard problems. As, by Proposition 5, the polycyclic languages are
closed under concatenation, this gives us a method to construct NP-complete
constrained synchronization problems with polycyclic constraint languages.
Proposition 8. Suppose we find u, v P Σ ˚ such that we can write L “ uv ˚ U
for some non-empty language U Ď Σ ˚ with
u R Factpv ˚ q, v R FactpU q, 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 , δ 1 q 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 ϕi pqq “ qi . Also, to simplify the formulas, set Q “ Q0 and ϕ0 : Q Ñ Q the
identity map. Choose some ŝ P S. Then, for r P Q1 and x P Σ we define
$
’ ϕi`1 pqq Di P t0, 1, . . . , n ´ 2u : r P Qi , r “ ϕi pqq, x “ xi`1 ;
’
δpq, cq r P Qn´1 , r “ ϕn´1 pqq, x “ xn ;
’
’
’
’
ŝ Di P t0, 1, . . . , n ´ 1u : r P Qi , r “ ϕi pqq, q R T Y S, x ‰ xi`1 ;
&
1
δ pr, xq “
’
’ q Di P t0, 1, . . . , n ´ 1u : r P Qi , r “ ϕi pqq, q P S, x ‰ xi`1 ;
t Di P t0, 1, . . . , n ´ 1u : r P Qi , r “ ϕi pqq, q P T, x ‰ xi`1 ;
’
’
’
’
t r “ t.
%
On a Class of Constrained Synchronization Problems in NP 11
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 (1)
and for q, q 1 P Q
δpq, cq “ q 1 in A ô δ 1 pq, v |u| q “ q 1 in A1 . (2)
1. Suppose we have cm such that δpS, cm q Ď T in A. Because u is not a factor
of v 2|u| , by construction of A1 , we have δ 1 pQ1 zpT Y ttuq, uq “ S, where S is
reached as |u| ď |v |u| |. This yields δ 1 pQzpT Yttuq, uam q Ď T . By construction
of A1 , δ 1 pT, xq “ ttu for any x P U X Σ ` , as x R Prefpv ˚ q and v is not a
factor of x. Note that we need the last condition to ensure that we do not
do a transition from a state in Q to a state in Q in A1 , for if a word does
this, it must have v |u| as a prefix. Also δ 1 pT, uq “ ttu, as 0 ă |u| ď |v |u| | and
u R Prefpv ˚ q by the assumption u R Factpv ˚ q.
2. Suppose we have w P LpBq that synchronizes A1 . Then, as t is a trap state,
δ 1 pQ1 , wq “ ttu. Write uv m x with x P U . By construction of A1 , we have,
as in the previous case, δ 1 pQzpT Y ttuq, uq “ S. Write m “ a|u| ` b with
0 ď b ă |u|. We argue that we must have δ 1 pS, v a|u| q Ď T . For assume we
have q P S with δ 1 pq, v a|u| q R T , then δ 1 pq, v a|u|`b q P Qb¨|v| by construction
of A1 . As S X T “ H, and hence q R T , by construction of A1 , this gives
δ 1 pq, v m xq P S Y Q1 Y . . . Y Q|v|´1 , as x is not a prefix of v and does not
contain v as a factor. More specifically, to go from q 1 P Qb|v| to Qpb`1q|v| , or
Q in case b ` |v| “ n, we have to read v. But x does not contain v as a factor.
By construction of A1 , for any y P Σ |v| ztvu, we have δ 1 pq 1 , yq P S if q 1 P Q|v|b .
This gives that if x “ x1 x2 x3 with |x2 | ď |v| and δ 1 pq, v m x1 q P S we have
δ 1 pq, v m x1 x2 q P S Y Q1 Y . . . Y Q|v|´1 , as after reading at most |v| symbols
of any factor of x, starting in a state from S, we must return to this state
at least once while reading this factor. Note that by the above reasoning we
find a prefix x1 of x with |x1 | ď |v| such that δ 1 pq, v m x1 q P S in case |x| ě |v|.
If |x| ă |v|, then either δ 1 pq 1 , xq P Q|b|`|x| or δ 1 pq 1 , xq P S. So, in no case could
we end up in the state t. Hence, we must have δ 1 pq, v a|u| q P T for each q P S.
By Equation (2) we get δpS, ca q Ď T .
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 Conclusion
We introduced the class of polycyclic automata and showed that for polycyclic
constraint automata, the constrained synchronization problem is in NP. For these
12 S. Hoffmann
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 au-
tomata 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 inter-
esting. 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 nondeter-
ministic 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.
References
1. Amarilli, A., Paperman, C.: Topological sorting with regular constraints. In:
Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th Interna-
tional Colloquium on Automata, Languages, and Programming, ICALP 2018, July
9-13, 2018, Prague, Czech Republic. LIPIcs, vol. 107, pp. 115:1–115:14. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik (2018)
2. Blondin, M., Krebs, A., McKenzie, P.: The complexity of intersecting finite au-
tomata having few final states. Comput. Complex. 25(4), 775–814 (2016)
3. Černý, J.: Poznámka k homogénnym experimentom s konečnými automatmi.
Matematicko-fyzikálny časopis 14(3), 208–216 (1964)
4. Diekert, V.: Makanin’s algorithm for solving word equations with regular con-
straints. Report, Fakultät Informatik, Universität Stuttgart (03 1998)
5. Diekert, V., Gutiérrez, C., Hagenah, C.: The existential theory of equations with
rational constraints in free groups is PSPACE-complete. Inf. Comput. 202(2), 105–
140 (2005), https://doi.org/10.1016/j.ic.2005.04.002
6. Eggan, L.C.: Transition graphs and the star-height of regular events. The Michigan
Mathematical Journal 10(4), 385–397 (Dec 1963)
7. Eilenberg, S.: Automata, Languages, and Machines, Volume A. Academic Press,
Inc., Orlando, FL, USA (1974)
8. Fernau, H., Gusev, V.V., Hoffmann, S., Holzer, M., Volkov, M.V., Wolf, P.: Compu-
tational complexity of synchronization under regular constraints. In: Rossmanith,
P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathemat-
ical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen,
Germany. LIPIcs, vol. 138, pp. 63:1–63:14. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik (2019), https://doi.org/10.4230/LIPIcs.MFCS.2019.63
9. Gusev, V.V.: Synchronizing automata of bounded rank. In: Moreira, N., Reis, R.
(eds.) Implementation and Application of Automata - 17th International Confer-
ence, CIAA. LNCS, vol. 7381, pp. 171–179. Springer (2012)
On a Class of Constrained Synchronization Problems in NP 13
10. Hoffmann, S.: Computational complexity of synchronization under regular com-
mutative constraints (accepted for publication in COCOON 2020). CoRR
abs/2005.04042 (2020), https://arxiv.org/abs/2005.04042
11. Hoffmann, S.: Constraint synchronization with two or three state partial constraint
automata. CoRR abs/2005.05907 (2020), https://arxiv.org/abs/2005.05907
12. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory,
Languages, and Computation. Addison-Wesley, 2nd edn. (2001)
13. Luks, E.M., McKenzie, P.: Parallel algorithms for solvable permutation groups. J.
Comput. Syst. Sci. 37(1), 39–62 (1988)
14. Martyugin, P.V.: Synchronization of automata with one undefined or ambiguous
transition. In: Moreira, N., Reis, R. (eds.) Implementation and Application of Au-
tomata - 17th International Conference, CIAA. LNCS, vol. 7381, pp. 278–288.
Springer (2012)
15. Pesant, G.: A regular language membership constraint for finite sequences of vari-
ables. In: Wallace, M. (ed.) Principles and Practice of Constraint Programming -
CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September
27 - October 1, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3258,
pp. 482–495. Springer (2004)
16. Robinson, D.J.: A Course in the Theory of Groups. Springer, 2 edn. (1995)
17. Romeuf, J.: Shortest path under rational constraint. Inf. Process. Lett. 28(5), 245–
248 (1988), https://doi.org/10.1016/0020-0190(88)90198-6
18. Rystsov, I.K.: Reset words for commutative and solvable automata. Theoretical
Computer Science 172(1-2), 273–279 (1997)
19. Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., Jonsson, B.,
Katoen, J.P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive
Systems. LNCS, vol. 3472, pp. 5–33. Springer (2005)
20. Schützenberger, M.P., Lyndon, R.C.: The equation aM=bNcP in a free group.
Michigan Mathematical Journal 9(4), 289–298 (1962)
21. Volkov, M.V.: Synchronizing automata and the Černý conjecture. In: Martı́n-Vide,
C., Otto, F., Fernau, H. (eds.) Language and Automata Theory and Applications,
2nd Int. Conference, LATA. LNCS, vol. 5196, pp. 11–27. Springer (2008)