# Careful Synchronization of One-Cluster Automata

Jakub Ruszil

(July 2023)

###### Abstract

In this paper we investigate careful synchronization of one-cluster partial
automata. First we prove that in general case the shortest carefully
synchronizing word for such automata is of length $2^{\frac{n}{2}}+1$, where
$n$ is the number of states of an automaton. Additionally we prove that
checking whether a given one-cluster partial automaton is carefully
synchronizing is NP-hard even in the case of binary alphabet.

##  1 Introduction

The concept of synchronization of finite automata is essential in various
areas of computer science. It consists in regaining control over a system by
applying a specific set of input instructions. These instructions lead the
system to a fixed state no matter in which state it was at the beginning. The
idea of synchronization has been studied for many classes of complete
deterministic finite automata (DFA) [2, 3, 8, 12, 13, 19, 21, 24, 26, 25, 27,
28] and non-deterministic finite automata [9, 10]. One of the most famous
longstanding open problems in automata theory, known as Černý Conjecture,
states that for a given synchronizing DFA with $n$ states one can always find
a synchronizing word of length at most $(n-1)^{2}$. This conjecture was proven
for numerous classes of automata, but the problem is still not solved in
general case. The concept of synchronization has been also considered in
coding theory [5, 11], parts orienting in manufacturing [8, 18], testing of
reactive systems [22] and Markov Decision Processes [6, 7].

Allowing no outgoing transitions from some states for certain letters helps us
to model a system for which certain actions cannot be accomplished while being
in a specified state. This leads to the problem of finding a synchronizing
word for a finite automaton, where transition function is not defined for all
states. Notice that this is the most frequent case, if we use automata to
model real-world systems. In practice, it rarely happens that a real system
can be modeled with a DFA where transition function is total. The transition
function is usually a partial one. This fact motivated many researchers to
investigate the properties of partial finite automata relevant to practical
problems of synchronization.
We know that, in general case, checking if a partial automaton can be
carefully synchronized is PSPACE-complete [15] even for binary alphabet [29].
In this paper we investigate the case of deterministic finite automata such
that transition from state to state is not necessary defined for all states.
We refer to this model as partial finite automaton (PFA). We will say that a
word which synchronizes a PFA is carefully synchronizing word. There exists
also different definition of synchronization of PFAs, for example in here [4].
The problem of estimating the length of a shortest carefully synchronizing
word for PFA was considered, among others, by Rystsov [20], Ito and
Shikishima-Tsuji [10], Martyugin [16, 17], Gazdag et. al. [30] and de Bondt
et. al. [14]. Martyugin established a lower bound on the length of such words
of size $\Theta(3^{n/3})$ and Rystsov [20] established an upper bound of size
$O((3+\epsilon)^{n/3})$, where $n$ is the number of states of the automaton.
One-cluster DFAs are the ones having a letter that has only one simple cycle
on the set of states. Synchronization of one-cluster DFA’s was studied by
Steinberg, Béal and Perrin and resulted in proving Černý Conjecture for one-
cluster automata with prime length cycle in [23] and establishing quadratic
upper bound for the length of the synchronizing word in general case in [1]
using linear algebra approach. However we also know that in general case
deciding if an automaton is synchronizing is in P what is not true in the case
of careful synchronization. Following that researches we extend the notion of
one-cluster to partial automata. Our research is motivated by the fact, that
all former constructions providing high careful synchronization threshold does
not contain a letter which creates a cluster on the set of states.
Constructions from [16, 17] have linear alphabet size in terms of cardinality
of the set of states but only one letter is defined for all states and the
number of clusters grows also linearly in the size of the set of states for
that letter. Cases from [29] and [14] are more interesting as they are dealing
with constant alphabet size, but constructions from that papers also do not
define any letter to be a one cluster (one of families of automata from [14],
used in the proof of Lemma 7 has one letter defined as a permutation on the
set of states with three cycles). On the other hand binary partial one cluster
automata have simple structural condition concerning non-cluster letter
(stated in latter Observation 1) which gives the impression that deciding
careful synchronizability of such automata is an easy problem in terms of
complexity theory. Suprisingly we managed to show that this decision problem
is hard even in such restricted case. Our contribution is twofold. First we
prove that in general case the shortest carefully synchronizing words for one-
cluster partial automata can be of exponential size in terms of the number of
states (but assuming alphabet is also of exponential size). From the
complexity perspective we show that the problem of deciding if a given binary
one-cluster PFA admits any carefully synchronizing word is NP-hard by
reduction from 3-SAT problem.

##  2 Preliminaries

A _partial finite automaton_ (PFA) is an ordered tuple
$\mathcal{A}=(\Sigma,Q,\delta)$ where $\Sigma$ is a finite set of letters, $Q$
is a finite set of states and $\delta:{Q\times\Sigma}\rightarrow{Q}$ is a
transition function, not everywhere defined. For $\emph{w}\in\Sigma^{\ast}$
and $\emph{q}\in Q$ we define $\delta(\emph{q},\emph{w})$ inductively:
$\delta(\emph{q},\epsilon)=q$ and
$\delta(\emph{q},\emph{aw})=\delta(\delta(\emph{q},\emph{a}),\emph{w})$ for
$a\in\Sigma$, where $\epsilon$ is the empty word and
$\delta(\emph{q},\emph{a})$ is defined. Let $S\subseteq Q$. Define
$\delta(S,w)=\bigcup_{q\in S}\delta(q,w)$. We write $q.w$ (respectively $S.w$
for a image of a set $S\subseteq Q$) instead of $\delta(q,w)$ (respectively
$\delta(S,w)$) wherever it does not cause ambiguity. We also denote
$S.w^{-1}=\\{q\in Q:q.w\in S\\}$ as a preimage of $S$ under the word $w$. A
word $\emph{w}\in\Sigma^{\ast}$ is called _carefully synchronizing_ if there
exists $\overline{q}\in Q$ such that for every $\emph{q}\in Q$,
$\delta(\emph{q},\emph{w})=\overline{q}$ and all transitions are defined. A
PFA is called _carefully synchronizing_ if it admits any carefully
synchronizing word. For a given $\mathcal{A}=(Q,\Sigma,\delta)$ we define the
_power-automaton_ $\mathcal{P}(\mathcal{A})=(2^{Q},\Sigma,\tau)$, where
$2^{Q}$ stands for the set of all subsets of $Q$. Transition function
$\tau:{2^{Q}\times\Sigma}\rightarrow{2^{Q}}$ is defined as follows:
$\tau(Q^{\prime},a)=\bigcup_{q\in Q^{\prime}}\delta(q,a)$, $a\in\Sigma$,
$Q^{\prime}\subseteq Q$ if $\delta(q,a)$ is defined for all states in $q\in
Q^{\prime}$. Otherwise $\tau(Q^{\prime},a)$ is not defined. We also consider a
deterministic finite automaton DFA. The only difference comparing to a PFA is
that the transition function is total in this case. All definitions regarding
PFA also apply to DFA, but we speak rather about synchronization than careful
synchronization in the case of DFA. We can now state an obvious fact, useful
to decide whether a given PFA is carefully synchronizing.

######  Fact 1.

Let $\mathcal{A}$ be a PFA and $\mathcal{P(A)}$ be its power automaton. Then
$\mathcal{A}$ is synchronizing if and only if for some state $q\in Q$ there
exists a labelled path in $\mathcal{P(A)}$ from $Q$ to $\\{q\\}$. The shortest
synchronizing word for $\mathcal{A}$ corresponds to the shortest such labelled
path in $\mathcal{P(A)}$.

An example of the carefully synchronizing automaton $\mathcal{A}_{car}$ is
depicted in Fig. 1. Its shortest carefully synchronizing word $w_{car}$ is
$abc(ab)^{2}c^{2}a$, which can be easily checked via the power automaton
construction.

$0$$1$$2$$3$a,cabab,cab,c Figure 1: A carefully synchronizing
$\mathcal{A}_{car}$

Let
$\mathcal{L}_{n}=\\{\mathcal{A}=(\Sigma,Q,\delta):\mathcal{A}\;is\;carefully\;synchronizing\;and\;|Q|=n\\}$.
Notice that $\mathcal{L}_{n}$ does not depend on alphabet size. We define
$d(\mathcal{A})=\min\\{|w|:w\;is\;a\;carefully\;synchronizing\>word\;for\;\mathcal{A}\\}$
and $d(n)=\max\\{d(\mathcal{A}):\mathcal{A}\in\mathcal{L}_{n}\\}$.
It can be easily verified from Fig 1. that the Černý Conjecture is not true
for PFAs, since $d(\mathcal{A}_{car})=10>(4-1)^{2}=9$.
For $\mathcal{A}=(Q,\Sigma,\delta)$ and $a\in\Sigma$ defined for all the
states let $\mathcal{G}_{a}=(Q,E)$ be a directed graph such that $(p,q)\in E$
if, and only if $p.a=q$. Put differently $\mathcal{G}_{a}$ is a digraph made
of only the edges labelled by $a$ in $\mathcal{A}$. The graph
$\mathcal{G}_{a}$ is a disjoint union of weakly connected components called
$a$-clusters. Since each state has only one outgoing edge in
$\mathcal{G}_{a}$, each $a$-cluster contains a unique cycle, called $a$-cycle
with trees attached to a cycle at their roots. For each $p\in Q$ we define a
level of $p$ as a distance between $p$ and the root of a tree containing $p$
in $\mathcal{G}_{a}$. The level of $\mathcal{G}_{a}$ is the maximal level of
its vertices. An example of the $a$-cluster is shown in Figure 3. One can
easily deduce from Fact 1 that at least one letter $a\in\Sigma$ must be
defined for all the states of the PFA in order for it to be carefully
synchronizing. We define a one-cluster PFA with respect to a letter $a$ as a
PFA which has only one $a$-cluster. We also refer to a one-cluster PFA as an
automaton which is one-cluster with respect to any of its letters.

$\displaystyle a$$\displaystyle a$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a$ Figure 2: Example of the $a$-cluster

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be a PFA, $a\in\Sigma$, $S\subset Q$ and
$G=(V,E)$ be a digraph. We say that _$S$ induces $G$ on the letter $a$ in
$\mathcal{A}$_, if a set $S$ induces in $\mathcal{G}_{a}$ a graph isomorphic
to $G$. Whenever not stated differently in the paper, when we refer to a one-
cluster automata, we assume that it is one-cluster with respect to a letter
$a$. Before moving further we state preliminary observation and lemma that can
shed more light on the matter of synchronization and careful synchronization
of one-cluster automata.

######  Observation 1.

If one-cluster automaton $\mathcal{A}=(Q,\Sigma,\delta)$ is carefully
synchronizing, $C$ induces a directed cycle on a letter $a$, letter $a$ is the
only one defined for all the states and $|C|>1$, then there exist letter
$b\in\Sigma$ such that $b\neq a$ and for any $q\in C$ it holds that
$\delta(q,b)$ is defined.

###### Proof.

Obviously, since $a$ is the only letter defined for all the states, then every
synchronizing word must start with it. On the other hand for all
$k\in\mathbb{N}$ holds $C\subseteq Q.a^{k}$ and if $k\geq l$, where $l$ is the
level of $\mathcal{G}_{a}$, then $Q.a^{k}=C$. If $|C|>1$, then there must
exits another letter $b\in\Sigma$ such that $C.b\neq C$ in order for
$\mathcal{A}$ to be carefully synchronizing. ∎

Now we state and proof a lemma that shows, that if there exist a word $w$ that
shrinks the set of the states that induces a directed cycle on $a$, then there
exist a word $w^{\prime}$ (polynomial in $|w|$) that shrinks the same subset
by a half.

######  Lemma 1.

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be a one-cluster PFA, $|Q|=n$, let $C$
induce a directed cycle on a letter $a$ and $l$ be the level of
$\mathcal{G}_{a}$. If there exist a word $w$ such that $|C.w|<|C|$ then there
exist a word $w^{\prime}$ such that
$|Q.w^{\prime}|\leq\lfloor\frac{1}{2}|C|\rfloor$ of length at most
$n+\frac{1}{2}|C|(|w|+|C|)$.

###### Proof.

For any $p,q\in C$ define
$\text{dist}_{C}(p,q)=\text{min}\\{k_{1},k_{2}:p.a^{k_{1}}=q\land
q.a^{k_{2}}=p\land k_{1},k_{2}<|C|\\}$. Since $p,q\in C$, then $dist_{C}(p,q)$
is always well defined and for all $p,q$ holds
$dist_{C}(p,q)\leq\lfloor\frac{1}{2}|C|\rfloor$. Since there exist $w$ such
that $|C|>|C.w|$, then there must exist $\bar{p},\bar{q}\in C$ such that
$\bar{p}.w=\bar{q}.w$. Denote $\text{dist}_{C}(\bar{p},\bar{q})=k$. We will
show claim:

######  Claim 1.

For any $C^{\prime}\subset C$ such that $|C^{\prime}|>\frac{1}{2}|C|$, there
exist $p^{\prime},q^{\prime}\in C$, such that
$\text{dist}(p^{\prime},q^{\prime})=k$.

###### Proof.

For the sake of contradiction suppose that there exist $C^{\prime}\subset C$
and $|C^{\prime}|>\frac{1}{2}|C|$ such that for all $p,q\in C^{\prime}$ holds
$\text{dist}(p,q)\neq k$. Let $S=\\{q_{i+k\text{ mod }m}:q_{i}\in
C^{\prime}\\}$. Since for any $q_{i}\in C^{\prime}$ there exist exactly one
state $q_{i+k\text{ mod }m}\in C$, then $|C^{\prime}|=|S|$. On the other hand,
since for all $p,q\in C^{\prime}$ holds $\text{dist}(p,q)\neq k$, then $C\cap
S=\varnothing$. But since $|C^{\prime}|=|S|>\frac{1}{2}|C|$ and
$C^{\prime}\subset C$ and $S\subset C$ then $|C^{\prime}|+|S|>|C|$ so there
must hold $C^{\prime}\cap S\neq\varnothing$ and we have a contradiction. ∎

We can construct a word $w^{\prime}$ in the following way: Obviously
$Q.a^{l}=C$ and $|Q.a^{l}w|<|C|$. If also
$|Q.a^{l}w|\leq\lceil\frac{1}{2}|C|\rceil$ then result holds. Otherwise
observe that $Q.a^{l}wa^{l}\subset C$ and $|Q.a^{l}wa^{l}|>\frac{1}{2}|C|$ so
we can apply Claim 1 to find states $p^{\prime},q^{\prime}\in Q.a^{l}wa^{l}$
such that $\text{dist}(p^{\prime},q^{\prime})=k=\text{dist}(\bar{p},\bar{q})$.
Denote $u=a^{l}wa^{l}$ and observe that for some $m_{1}\leq|C|<n$ it must hold
that $\bar{p},\bar{q}\in Q.ua^{m_{1}}$ so $|Q.ua^{m_{1}}w|<|Q.u|$. We can
apply Claim 1 and word $a^{m_{1}}w$ as long as the size of the resulting set
is greater than $\frac{1}{2}|C|$. We obtain the word
$w^{\prime}=a^{l}w(a^{m_{1}}w)^{m}_{2}$ where $m_{2}<\frac{1}{2}|C|-1$ so the
result holds. ∎

##  3 Long shortest carefully synchronizing word

In this section we construct an infinite family of carefully synchronizing,
one-cluster PFAs with exponential shortest carefully synchronizing word. The
scheme of the proof is similar as in [10] (Proposition 8), however it differs
in details. In order to simplify the proofs we assume, that the size of the
set of states is $n=2k$, where $k\in\mathbb{N}$ but proofs can be easily
adapted to the case $n=2k+1$ achieving similar results. Let
$C_{k}=\\{c_{1},\ldots,c_{k}\\}$ and $T_{k}=\\{t_{1},\ldots,t_{k}\\}$,
$Q_{k}=C_{k}\cup T_{k}$ and $\Sigma_{k}=\\{a\\}\cup\Sigma_{k}^{\prime}$ where
$\Sigma_{k}^{\prime}$ is a set of letters specified later on. Finally let
$\mathcal{B}_{k}=(Q_{k},\Sigma_{k},\delta_{k})$. Define action of the letter
$a$ on the set of states:

  * •

$\delta_{k}(c_{i},a)=c_{i+1}$ for $i<k$

  * •

$\delta_{k}(c_{n},a)=c_{1}$

  * •

$\delta_{k}(t_{i},a)=c_{i}$

It is easy to observe that $\mathcal{B}_{k}$ is one-cluster with respect to
$a$ for every $k$. Example of that cluster for $k=3$ is depicted below.

$\displaystyle a$$\displaystyle a$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a$$\displaystyle c_{1}$$\displaystyle
c_{2}$$\displaystyle c_{3}$$\displaystyle t_{1}$$\displaystyle
t_{2}$$\displaystyle t_{3}$ Figure 3: The $a$-cluster of the automaton
$\mathcal{B}_{3}$

Let $\mathcal{T}_{k}=\\{T\cup(C_{k}\cap((T_{k}\setminus T).a).a^{-1}):T\in
2^{T_{k}}\setminus\\{\varnothing\\}\\}$ Intuitively it is the set of all sets
$T$ such that $|T^{\prime}|=k$ and $T^{\prime}.a=C_{k}$. First we prove a
simple lemma.

######  Lemma 2.

Let $\mathcal{T}_{k}$ be a family of sets defined above. Then
$|\mathcal{T}_{k}|=2^{|T_{k}|}-1$.

###### Proof.

Let $T^{\prime}_{1},T^{\prime}_{2}\in 2^{T_{k}}$ such that $T^{\prime}_{1}\neq
T^{\prime}_{2}$. Denote $C_{k}\cap((T_{k}\setminus
T^{\prime}_{1}).a).a^{-1}=P_{1}$ and $C_{k}\cap((T_{k}\setminus
T^{\prime}_{2}).a).a^{-1}=P_{2}$ It suffices to show that for any
$T^{\prime}_{1},T^{\prime}_{2}$ sets $T^{\prime}_{1}\cup P_{1}$ and
$T^{\prime}_{2}\cup P_{2}$ are different. But it is easy to notice that
$P_{1},P_{2}\subset C_{k}$ and since $T^{\prime}_{1}\neq T^{\prime}_{2}$ and
$T^{\prime}_{1},T^{\prime}_{2}\subset T_{k}$ then the lemma holds. ∎

Using Lemma 2 we can enumerate sets of family $\mathcal{T}_{k}$ arbitrarily
from $S_{1}$ to $S_{2^{|T_{k}|}-1}$. Let us prove properties of that sets in
the next lemma.

######  Lemma 3.

For any $i\in\\{1,\ldots,2^{|T_{k}|}-1\\}$ holds $S_{i}.a=C_{k}$ and
$|S_{i}|=\frac{n}{2}$.

###### Proof.

By definition of $S_{i}$ we know that there exist $T\subseteq T_{k}$ such that
$S_{i}=T\cup(C_{k}\cap((T_{k}\setminus T).a).a^{-1})$. By construction
$T.a\subseteq C$ so it suffices to show that $(C\cap((T_{k}\setminus
T).a).a^{-1}).a=C\setminus T.a$. Indeed $(C_{k}\cap((T_{k}\setminus
T).a).a^{-1}).a=C_{k}.a\cap(T_{k}\setminus T).a=C_{k}\cap T_{k}.a\setminus
T.a=C\cap C\setminus T.a=C\setminus T.a$. To show that $|S_{i}|=\frac{n}{2}$
first observe that $(T_{k}\setminus T).a=\\{q\in C_{k}\setminus T.a\\}$. Let
$q\in C_{k}\setminus T.a$ and observe that set $q.a^{-1}$ contains exactly two
states $q_{1}\in T_{k}$ and $q_{2}\in C_{k}$ and by the construction we have
that $|((T_{k}\setminus T).a).a^{-1}|=2|C_{k}\setminus T.a|$ and half of the
states must be contained in $C_{k}$ which gives us
$|S_{i}|=|T.a|+|C_{k}\setminus T.a|$ and that concludes the proof. ∎

Let $\Sigma_{k}^{\prime}=\\{b_{1},\ldots,b_{2^{|T_{k}|}-1},c\\}$ (this is the
subalphabet used in the definition of $\Sigma_{k}$) and
$S_{i}=\\{s_{1}^{i},\ldots,s_{k}^{i}\\}$. Put transition function $\delta_{k}$
(for $\Sigma_{k}^{\prime}$) as follows:

  * •

$\delta_{k}(c_{j},b_{1})=s_{j}^{1}$, letter $b_{1}$ not defined for other
states

  * •

for $0<i<2^{|T_{k}|}-2$ let $\delta_{k}(s_{j}^{i},b_{i+1})=s_{j}^{i+1}$,
letter $b_{i}+1$ not defined for other states

  * •

$\delta_{k}(s_{j}^{2^{|T_{k}|}-1},c)=c_{1}$, letter $c$ not defined for other
states

Observe that for any $i$ holds $\delta_{k}(S_{i},b_{i+1})=S_{i+1}$. Let us
state and prove the main theorem in this section.

######  Theorem 1.

Automaton $\mathcal{B}_{k}$ is carefully synchronized by a word
$w=ab_{1}\ldots b_{2^{|T_{k}|}-1}c$, $w$ is the shortest word that carefully
synchronizes $\mathcal{B}_{k}$ and $|w|=2^{\frac{n}{2}}+1$.

###### Proof.

Since $\mathcal{B}_{k}$ is one clustered with respect to $a$ and the level of
that cluster is $1$, it is straightforward that $Q.a=C$. Immediately from the
construction we have that for $w_{i}=ab_{1}\ldots b_{i}$ the equality
$Q.w_{i}=S_{i}$ holds and from that we have that $Q.w=c_{1}$ so $w$ carefully
synchronizes $\mathcal{B}_{k}$. In order to prove the minimality of $w$ first
notice that for each $i$ holds that $S_{i}.b_{j}$ is undefined for $j\neq i-1$
(because each $|S_{i}|=\frac{n}{2}$ from Lemma 3) and $S_{i}.a=C$ (by Lemma
3). Then $\mathcal{P}(\mathcal{B}_{k})$ forms a path from $Q$ to $\\{c_{1}\\}$
labelled with consecutive letters of $w$ and for each state on the path there
is only one transition leading to $C$ (visited in the first step of the path)
and that ends the proof. ∎

##  4 Complexity

This section is devoted to the proof that the problem of deciding whether a
given one-cluster PFA is carefully synchronizing is NP-hard even in the case
of binary alphabet. Notice that Observation 1 implies that, letter $b$ must be
defined for at least all states in the cycle induced by the letter $a$. Refer
to that problem as ONE-CLUSTER-CARSYNC. Let us state that theorem formally.

######  Theorem 2.

For a given PFA $\mathcal{A}=(Q,\\{a,b\\},\delta)$ that is one-cluster with
respect to $a$, the problem of deciding whether $\mathcal{A}$ has a carefully
synchronizing word (2-ONE-CLUSTER-CARSYNC) is NP-hard.

In order to prove the theorem we construct a polynomial time reduction from
3-SAT to 2-ONE-CLUSTER-CARSYNC. Let $\\{x_{1},\ldots,x_{n}\\}$ be a set of
variables and $C_{1},\ldots,C_{m}$ be clauses. We also assume that for any
pair $\\{x_{j},\bar{x}_{j}\\}$ if $x_{j}\in C_{i}$ then $\bar{x}_{j}\notin
C_{i}$. That is not really a problem, since if both of them belong to $C_{i}$,
then $C_{i}$ is always true. For a given formula $\phi=C_{1}\land\ldots\land
C_{m}$ we define a PFA $\mathcal{A}_{\phi}=(Q,\\{a,b\\},\delta_{\phi})$. Let
$Q=\bigcup_{i=1}^{m}(S_{C_{i}^{t}}\cup S_{C_{i}^{f}})\cup P\cup R$ where:

  * •

$P=\\{p_{1},\ldots,p_{m}\\}$

  * •

$R=\\{r_{1},\ldots,r_{m}\\}$

  * •

$S_{C_{i}^{t}}=\\{c_{i}^{x_{1}},\ldots,c_{i}^{x_{n}},x_{i}^{end}\\}$ for each
$i$

  * •

$S_{C_{i}^{f}}=\\{\bar{c}_{i}^{x_{1}},\ldots,\bar{c}_{i}^{x_{n}},\bar{x}_{i}^{end}\\}$
for each $i$.

Define $\delta_{\phi}$ in the following way:

  1. 1.

$\delta_{\phi}(p_{i},a)=p_{i+1\text{ mod }m}$

  2. 2.

$\delta_{\phi}(p_{i},b)=\bar{c}_{i}^{x_{1}}$

  3. 3.

$\delta_{\phi}(r_{i},a)=p_{i}$, $\delta_{\phi}(r_{i},b)$ undefined

  4. 4.

$\delta_{\phi}(c_{i}^{end},a)=\delta_{\phi}(\bar{c}_{i}^{end},a)=r_{i}$

  5. 5.

$\delta_{\phi}(c_{i}^{end},b)=p_{1}$ $\delta_{\phi}(\bar{c}_{i}^{end},b)$
undefined

  6. 6.

if $x_{j}\in C_{i}$ then
$\delta_{\phi}(\bar{c}_{i}^{x_{j}},a)=c_{i}^{x_{j+1}}$ otherwise
$\delta_{\phi}(\bar{c}_{i}^{x_{j}},a)=\bar{c}_{i}^{x_{j+1}}$ for $0<j<n$

  7. 7.

if $\bar{x}_{j}\in C_{i}$ then
$\delta_{\phi}(\bar{c}_{i}^{x_{j}},b)=c_{i}^{x_{j+1}}$ otherwise
$\delta_{\phi}(\bar{c}_{i}^{x_{j}},b)=\bar{c}_{i}^{x_{j+1}}$ for $0<j<n$

  8. 8.

$\delta_{\phi}(c_{i}^{x_{j}},a)=\delta_{\phi}(c_{i}^{x_{j}},b)=c_{i}^{x_{j+1}}$
for $0<j<n$

  9. 9.

if $x_{n}\in C_{i}$ then $\delta_{\phi}(\bar{c}_{i}^{x_{n}},a)=c_{i}^{end}$
otherwise $\delta_{\phi}(\bar{c}_{i}^{x_{n}},a)=\bar{c}_{i}^{end}$

  10. 10.

if $\bar{x}_{n}\in C_{i}$ then
$\delta_{\phi}(\bar{c}_{i}^{x_{n}},b)=c_{i}^{end}$ otherwise
$\delta_{\phi}(\bar{c}_{i}^{x_{n}},b)=\bar{c}_{i}^{end}$

  11. 11.

$\delta_{\phi}(c_{i}^{x_{n}},a)=\delta_{\phi}(c_{i}^{x_{n}},b)=c_{i}^{end}$

For the example formula $\phi_{ex}=(x_{1}\lor x_{3}\lor x_{4})\land(x_{1}\lor
x_{2}\lor\bar{x}_{3})\land(\bar{x}_{1}\lor\bar{x}_{2}\lor x_{4})$ the
corresponding $\mathcal{A}_{\phi_{ex}}$ is depicted in Fig. 4.

$\displaystyle p_{1}$$\displaystyle p_{2}$$\displaystyle p_{3}$$\displaystyle
r_{1}$$\displaystyle r_{2}$$\displaystyle r_{3}$$\displaystyle
c_{1}^{end}$$\displaystyle\overline{c}_{1}^{end}$$\displaystyle
c_{1}^{x_{4}}$$\displaystyle\overline{c}_{1}^{x_{4}}$$\displaystyle
c_{1}^{x_{3}}$$\displaystyle\overline{c}_{1}^{x_{3}}$$\displaystyle
c_{1}^{x_{2}}$$\displaystyle\overline{c}_{1}^{x_{2}}$$\displaystyle
c_{1}^{x_{1}}$$\displaystyle\overline{c}_{1}^{x_{1}}$$\displaystyle
c_{2}^{end}$$\displaystyle\overline{c}_{2}^{end}$$\displaystyle
c_{2}^{x_{4}}$$\displaystyle\overline{c}_{2}^{x_{4}}$$\displaystyle
c_{2}^{x_{3}}$$\displaystyle\overline{c}_{2}^{x_{3}}$$\displaystyle
c_{2}^{x_{2}}$$\displaystyle\overline{c}_{2}^{x_{2}}$$\displaystyle
c_{2}^{x_{1}}$$\displaystyle\overline{c}_{2}^{x_{1}}$$\displaystyle
c_{3}^{end}$$\displaystyle\overline{c}_{3}^{end}$$\displaystyle
c_{3}^{x_{4}}$$\displaystyle\overline{c}_{3}^{x_{4}}$$\displaystyle
c_{3}^{x_{3}}$$\displaystyle\overline{c}_{3}^{x_{3}}$$\displaystyle
c_{3}^{x_{2}}$$\displaystyle\overline{c}_{3}^{x_{2}}$$\displaystyle
c_{3}^{x_{1}}$$\displaystyle\overline{c}_{3}^{x_{1}}$$\displaystyle
a,b$$\displaystyle a$$\displaystyle a$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a$$\displaystyle b$$\displaystyle
b$$\displaystyle b$$\displaystyle b$$\displaystyle b$$\displaystyle
b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle
a,b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle
a,b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle a,b$$\displaystyle
a$$\displaystyle b$$\displaystyle a,b$$\displaystyle a$$\displaystyle
a$$\displaystyle b$$\displaystyle b$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a,b$$\displaystyle b$$\displaystyle
b$$\displaystyle b$$\displaystyle b$$\displaystyle a$$\displaystyle
a$$\displaystyle a$$\displaystyle a,b$$\displaystyle b$$\displaystyle b$
Figure 4: Automaton $\mathcal{A}_{\phi_{ex}}$

Let us state and prove two lemmas before going further.

######  Lemma 4.

For any given $\phi$ the automaton $\mathcal{A}_{\phi}$ is one-cluster with
respect to $a$.

###### Proof.

First observe that for any $\phi$ the set $P$ forms the $a$-cycle in the
automaton $\mathcal{A}_{\phi}$ (Point 1 of the definition of $\delta_{\phi}$).
It is also easy to see from the definition of $\mathcal{A}_{\phi}$ that any
set $S_{C_{i}^{t}}$ together with the states $r_{i}\in R$ and $p_{i}\in P$
creates a directed path of the form $c_{i}^{x_{1}}\rightarrow
c_{i}^{x_{2}}\rightarrow\ldots\rightarrow c_{i}^{x_{n}}\rightarrow
r_{i}\rightarrow p_{i}$ labelled with $a$ (Points 3, 4 and 8 of the definition
of $\delta_{\phi}$). Denote this path as $p$. Denote by $v_{j}$ a variable of
the formula $\phi$ and $v_{j}\in\\{x_{j},\bar{x}_{j}\\}$. Consider now clause
$C_{i}\in\phi$ and the set $S_{C_{i}^{f}}$. Assume that $C_{i}=(v_{j_{1}}\lor
v_{j_{2}}\lor v_{j_{3}})$ and $j_{1}<j_{2}<j_{3}$. Any of the variables
$v_{j_{3}+1},\ldots,v_{n}$ does not belong to clause $C_{i}$, so the set
$\\{\bar{c}_{i}^{x_{j_{3}+1}},\bar{c}_{i}^{x_{j_{3}+2}},\ldots,\bar{c}_{i}^{x_{n}},\bar{c}_{i}^{end},r_{i}\\}$
forms a directed path on the letter $a$ (Points 4, 6, 7, 9, 10 of the
definition of $\delta_{\phi}$). Denote it by $p_{1}$. Suppose that
$v_{j_{3}}=\bar{x}_{j_{3}}$. Then, by Points 6 or 9, state
$\bar{c}_{i}^{x_{j_{3}}}$ is attached to the first state of the path $p_{1}$
with a transition labelled by a letter $a$. Otherwise, by Points 6 or 9,
$\bar{c}_{i}^{x_{j_{3}}}$ is attached to the path $p$ by a letter $a$. Now we
can repeat our argument to the set
$\\{\bar{c}_{i}^{x_{j_{2}+1}},\ldots\bar{c}_{i}^{x_{j_{3}-1}}\\}$ to show that
it forms a path $p_{2}$ labelled with the letter $a$ which begins in the state
$\bar{c}_{i}^{x_{j_{2}+1}}$ and ends in the state $\bar{c}_{i}^{x_{j_{3}-1}}$.
By Point 6 we obtain, that this path is attached by its end to the state
$\bar{c}_{i}^{x_{j_{3}}}$ by the letter $a$. Now we can also repeat our
arguments to the state $\bar{c}_{i}^{x_{j_{2}+1}}$ to show that it is either
attached to $p_{2}$ or to $p$. Using the same reasoning for the sets
$\\{\bar{c}_{i}^{x_{j_{1}+1}},\ldots\bar{c}_{i}^{x_{j_{2}-1}}\\}$ and
$\\{\bar{c}_{i}^{x_{1}},\ldots\bar{c}_{i}^{x_{j_{2}-1}}\\}$ and state
$\bar{c}_{i}^{x_{j_{1}}}$ concludes the proof. ∎

######  Lemma 5.

For any given $\phi$, if $n_{1}<n+3$ then $\delta_{\phi}(Q,a^{n_{1}}b)$ is
undefined.

###### Proof.

Observe, that the letter $a$ induces a path on $n+3$ vertices on the set
$S_{C_{i}^{t}}\cup\\{r_{i},p_{i}\\}=S_{i}$ for each $i$. That path starts in
$c_{i}^{x_{1}}$, ends in $p_{i}$ and the one before last vertex on that path
is $r_{i}$. Also $Q=\bigcup_{i=1}^{m}S_{i}$, so for each $n_{1}<n+3$ holds
$r_{i}\in Q.a^{n_{1}}$ for any $0<i<m+1$. On the other hand
$\delta_{\phi}(r_{i},b)$ is undefined for each $i$ (Point 3), so
$\delta_{\phi}(Q,a^{n_{1}}b)$ is undefined and the lemma holds. ∎

Before moving further let us define, for a given $\mathcal{A}_{\phi}$, two
subsets of its states
$S_{init}=\\{\bar{c}_{1}^{x_{1}},\ldots,\bar{c}_{m}^{x_{1}}\\}$ and
$S_{end}=\\{c_{1}^{end},\ldots,c_{m}^{end}\\}$ and state the following
observation.

######  Observation 2.

For any $i\in\\{1,\ldots,m\\}$ and formula $\phi$, if $v\in\\{a,b\\}^{*}$ and
$|v|=n$, then
$\delta_{\phi}(\bar{c}_{i}^{x_{1}},v)\in\\{c_{i}^{end},\bar{c}_{i}^{end}\\}$.

###### Proof.

Immediate from Points 6 to 11 of definition of $\delta_{\phi}$. ∎

######  Lemma 6.

For any given $\phi$ automaton $\mathcal{A}_{\phi}$ is carefully synchronizing
if and only if there exist a word $w$ of length $n$ such that
$\delta_{\phi}(S_{init},w)=S_{end}$.

###### Proof.

First assume, that there exists a word $w$ of length $n$ such that
$\delta_{\phi}(S_{init},w)=S_{end}$. Observe that $\delta_{\phi}(Q,a^{n+3})=P$
and $\delta_{\phi}(P,b)=S_{init}$. Also $\delta_{\phi}(S_{init},w)=S_{end}$
and $\delta_{\phi}(S_{end},b)=p_{1}$ so we conclude that word $u=a^{n+3}bwb$
carefully synchronizes $\mathcal{A}_{\phi}$. Now assume that
$\mathcal{A}_{\phi}$ is carefully synchronizing. From Lemma 5 we obtain that
any carefully synchronizing word for $\mathcal{A}_{\phi}$, say
$u\in\\{a,b\\}^{*}$, must start with a word $a^{k}$ where $k>n+2$. Since
$\delta_{\phi}(Q,a^{n+3})=P$ and $\delta_{\phi}(P,a)=P$ we imply that $u$ must
be of the form $a^{k}bv$. We know that $\delta_{\phi}(Q,a^{k}b)=S_{init}$.
From Observation 2 for any $v_{1}\in\\{a,b\\}^{*}$ such that $|v_{1}|=n$ we
have
$\delta_{\phi}(\bar{c}_{i}^{x_{1}},v_{1})\in\\{c_{i}^{end},\bar{c}_{i}^{end}\\}$.
On the other hand observe that for any set of the form
$\\{t_{1},\ldots,t_{n}\\}$, where
$t_{i}\in\\{c_{i}^{end},\bar{c}_{i}^{end}\\}$ but $S_{end}$, we have that
$\delta_{\phi}(T,b)$ is undefined, $\delta_{\phi}(T,a)=R$ and
$\delta_{\phi}(R,b)$ is undefined, and $\delta_{\phi}(R,a)=P$. So, since $u$
carefully synchronizes $a$ there must exist desired word, which concludes the
proof. ∎

######  Lemma 7.

Let $\phi$ be a formula and $\mathcal{A}_{\phi}$ be a corresponding automaton.
Then $\phi$ has truth assignment if and only if there exists a word $w$ of
length $n$ such that $\delta_{\phi}(S_{init},w)=S_{end}$.

###### Proof.

First assume that $\phi$ has a truth assignment
$e:\\{x_{1},\ldots,x_{n}\\}\rightarrow\\{0,1\\}$. We define a word $w$ of
length $n$ in a following way: if $e(x_{i})=1$ in that evaluation then $i$-th
letter of the word $w$ is $a$, otherwise the $i$-th letter is $b$. Note
$w_{i}$ as $i-1$ letter prefix of $w$ and $\bar{w}_{i}$ as a $i-1$ letter
suffix of $w$. Let $0<k_{1}<k_{2}<k_{3}<n+1$ and consider clause
$C_{j}=y_{k_{1}}\lor y_{k_{2}}\lor y_{k_{3}}$ where
$y_{k_{i}}\in\\{x_{k_{i}},\bar{x}_{k_{i}}\\}$. Since $e$ is a truth
evaluation, then at least one of the variables $x_{k_{1}}$, $x_{k_{2}}$ or
$x_{k_{3}}$ must evaluate to true in the sense that if $y_{k_{i}}=x_{k_{i}}$
then $e(x_{k_{i}})=1$, otherwise $e(x_{k_{i}})=0$. It is straightforward from
the definition of $\delta_{\phi}$ (Points 6 and 7) that
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{1}})=\bar{c}_{j}^{x_{k_{1}}}$. Now
consider four pairwise exclusive cases:

  1. 1.

$y_{k_{1}}=x_{k_{1}}$ and $e(x_{k_{1}})=1$

  2. 2.

$y_{k_{1}}=x_{k_{1}}$ and $e(x_{k_{1}})=0$

  3. 3.

$y_{k_{1}}=\bar{x}_{k_{1}}$ and $e(x_{k_{1}})=1$

  4. 4.

$y_{k_{1}}=\bar{x}_{k_{1}}$ and $e(x_{k_{1}})=0$.

Now:

  * •

if case 1 holds, then $i$-th letter of $w$ is $a$ and by Point 6 we know that
$\delta_{\phi}(\bar{c}_{j}^{x_{k_{1}}},a)=c_{j}^{x_{k_{1}+1}}$

  * •

if case 2 holds, then $i$-th letter of $w$ is $b$ and by Point 7 we know that
$\delta_{\phi}(\bar{c}_{j}^{x_{k_{1}}},b)=\bar{c}_{j}^{x_{k_{1}+1}}$

  * •

if case 3 holds, then $i$-th letter of $w$ is $a$ and by Point 6 we know that
$\delta_{\phi}(\bar{c}_{j}^{x_{k_{1}}},a)=\bar{c}_{j}^{x_{k_{1}+1}}$

  * •

if case 4 holds, then $i$-th letter of $w$ is $b$ and by Point 7 we know that
$\delta_{\phi}(\bar{c}_{j}^{x_{k_{1}}},b)=c_{j}^{x_{k_{1}+1}}$.

If case 1 or 4 hold, then
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{i+1})=c_{j}^{x_{k_{1}+1}}$ and, from
Points 8 and 11 we obtain that
$\delta_{\phi}(c_{j}^{x_{k_{1}+1}},\bar{w}_{n-k_{1}})=c_{j}^{end}$. Otherwise
we obtain that
$\delta(\bar{c}_{j}^{x_{1}},w_{k_{2}})=\delta(\bar{c}_{j}^{x_{k_{2}}})$ and we
can repeat our case analysis to obtain that either
$\delta(\bar{c}_{j}^{x_{1}},w_{k_{2}+1})=c_{j}^{x_{k_{2}+1}}$ (if $y_{k_{2}}$
evaluates to true) or
$\delta(\bar{c}_{j}^{x_{1}},w_{k_{2}+1})=\bar{c}_{j}^{x_{k_{2}+1}}$ (if
$y_{k_{2}}$ evaluates to false). With the same argument applied to
$y_{k_{3}}$, since at least one of the variables of $C_{j}$ must be evaluated
to true, we obtain that $\delta_{\phi}(\bar{c}_{j}^{x_{1}},w)=c_{j}^{end}$.
But since $e$ is a truth evaluation, then any $C_{j}$ must have at least one
variable evaluated to true, so for any $j\in\\{1,\ldots,m\\}$ we have that
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w)=c_{j}^{end}$, so we obtain that
$\delta(S_{init},w)=S_{end}$.
Now assume that there exist a word $w$ of length $n$, such that
$\delta(S_{init},w)=S_{end}$. We define the evaluation of $\phi$,
$e_{w}:\\{x_{1},\ldots,x_{n}\\}\rightarrow\\{0,1\\}$ in the following way: if
$i$-th letter of $w$ is $a$, then $e_{w}(x_{i})=1$ otherwise $e_{w}(x_{i})=0$.
Since $\delta_{\phi}(S_{init},w)=S_{end}$, then from Observation 2 for any
$j\in\\{1,\ldots,m\\}$ holds
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w)=c_{j}^{end}$. Consider evaluation
$e_{w}$ and let $0<k_{1}<k_{2}<k_{3}<n+1$ and clause $C_{j}=y_{k_{1}}\lor
y_{k_{2}}\lor y_{k_{3}}$ where $y_{k_{i}}\in\\{x_{k_{i}},\bar{x}_{k_{i}}\\}$.
It suffices to prove that for any $j$ if
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w)=c_{j}^{end}$, then $e_{w}(y_{k_{1}})=1$
or $e_{w}(y_{k_{1}})=1$ or $e_{w}(y_{k_{1}})=1$ (we assume here that
$e(\bar{x})=1-e(x)$). For the sake of contradiction suppose, that there exist
$j\in\\{1,\ldots,m\\}$ such that
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w)=c_{j}^{end}$ and $e_{w}(y_{k_{1}})=0$
and $e_{w}(y_{k_{2}})=0$ and $e_{w}(y_{k_{3}})=0$. First observe that
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{1}})=\bar{c}_{j}^{x_{k_{1}}}$. Since
$e(y_{k_{1}})=0$, then (from Points 6 and 7) we obtain that
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{1}+1})=\bar{c}_{j}^{x_{k_{1}+1}}$.
The same argument for $y_{2}$ gives us
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{2}+1})=\bar{c}_{j}^{x_{k_{2}+1}}$
(from Points 6 and 7) and further for $y_{3}$
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{3}+1})=\bar{c}_{j}^{x_{k_{3}+1}}$ or
$\delta_{\phi}(\bar{c}_{j}^{x_{1}},w_{k_{3}+1})=\bar{c}_{j}^{end}$
(respectively from Points 6 and 7 or 10 and 11). In the latter case we obtain
contradiction straightforward and in the former we notice, that for any
$v\in\\{a,b\\}^{*}$ such that $|v|=n-k_{3}$ we obtain that
$\delta_{\phi}(\bar{c}_{j}^{x_{k_{3}}},v)=\bar{c}_{j}^{end}$ (from Points 6,
7,10 and 11 and observation that any variable with index greater than $k_{3}$
does not belong to the clause $C_{j}$). That concludes the proof. ∎

Combining Lemmas 6 and 7 we obtain that automaton $\mathcal{A}_{\phi}$ is
carefully synchronizing if, and only if formula $\phi$ has a truth evaluation.
Taking Lemma 4 into account, the only thing we have to prove in order to
finish the proof of Theorem 2 is that the reduction can be performed in
polynomial time. Observe that, for any $\phi$ with $n$ variables and $m$
clauses and corresponding $\mathcal{A}_{\phi}$ we have that $|P|=|R|=m$ and
for any $i\in\\{1,\ldots,m\\}$ holds also
$|S_{C_{i}^{t}}|=|S_{C_{i}^{f}}|=n+1$, we obtain, that $|Q|=2m(n+2)$ and on
the other hand $\mathcal{A}_{\phi}$ is a partial automaton, what means, that
for any state there are at most two outgoing transitions ($a$ and $b$), so
computing automaton $\mathcal{A}_{\phi}$ can be done in polynomial size of $n$
and $m$ and that concludes the proof of Theorem 2.

##  5 Conclusions

In Section 3 we have found infinite family of PFAs with shortest carefully
synchronizing words of exponential length. However the size of the alphabet
used in the construction is also exponential in terms of the number of states
and that makes the construction not sufficient to make analysis of decision
problem as stated in Section 4. An interesting problem to investigate is if
one can achieve exponentially long shortest carefully synchronizing word for
one-cluster PFAs, but using smaller alphabet size.
In Section 4 we have proven NP-hardness of the problem of deciding whether a
given binary one-cluster PFAs can be carefully synchronized. Let $\mathcal{A}$
be a one cluster PFA with respect to a letter $a$ and let $C$ be a set of
states that induces a cycle on letter $a$. Further analysis of the proof of
NP-hardness leads to a conclusion that even the problem of deciding whether
there exist a word $w$ such that $|C.w|<|C|$ is also NP-hard. Let us make a
simple observation:

######  Observation 3.

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be a PFA, and $w\in\Sigma^{*}$. There
exist an algorithm that, in $O(|w||Q|)$ time complexity decides whether $w$ is
a carefully synchronizing word for $\mathcal{A}$.

###### Proof.

Consider algorithm defined below:

$P\leftarrow Q$

for $i=0,i<|w|,i\leftarrow i+1$ do

$P\leftarrow P.w[i]$

end for

if $|P|=1$ then

return true

else

return false

end if

Obviously algorithm answers true if and only if $w$ carefully synchronizes
$\mathcal{A}$ and requires $O(|Q|)$ additional space complexity and
$O(|Q||w|)$ time complexity, what concludes the proof. ∎

From Observation 3 we can infer that one possibility to prove that the problem
2-ONE-CLUSTER-CARSYNC is in NP is to prove that the shortest carefully
synchronizing word for binary one-cluster automata is of polynomial length, a
problem that we what we want to investigate in further research. Lemma 1 can
be utilized in the proof of that result. One must show first that if there
exist a word $w$ such that $|C.w|<C$ where $C$ is the set of states inducing a
cycle on the letter $a$, then such a word is of polynomial length in terms of
the set of states. Next question is how to synchronize the remaining half of
the states of the cycle.

## References

  * [1] Marie-Pierre Béal and Dominique Perrin.  A quadratic upper bound on the size of a synchronizing word in one-cluster automata.  In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, pages 81–90, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [2] M. Berlinkov.  On Two Algorithmic Problems about Synchronizing Automata.  Language and Automata Theory and Applications, pages 61–67, 2014\.
  * [3] M. Berlinkov and M. Szykuła.  Algebraic Synchronization Criterion and Computing Reset Words.  Information Sciences, 369:718–730, 2016.
  * [4] Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła.  Synchronizing Strongly Connected Partial DFAs.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2021/13657, doi:10.4230/LIPIcs.STACS.2021.12.
  * [5] M. T. Biskup and W. Plandowski.  Shortest Synchronizing Strings for Huffman Codes.  Theoretical Computer Science, 410:3925–3941, 2009.
  * [6] L. Doyen, T. Massart, and M. Shirmohammadi.  Robust Synchronization in Markov Decision Processes.  CONCUR, pages 234–248, 2014.
  * [7] L. Doyen, T. Massart, and M. Shirmohammadi.  The Complexity of Synchronizing Markov Decision Processes.  J. Comput. Syst. Sci., 100:96–129, 2019.
  * [8] D. Eppstein.  Reset Sequences for Monotonic Automata.  SIAM J. of Computing, 19:500–510, 1990.
  * [9] B. Imreh and M. Steinby.  Directable Nondeterministic Automata.  Acta Cybern., 14:105–115, 1999.
  * [10] M. Ito and K. Shikishima-Tsuji.  Some Results in Directable Automata.  Theory Is Forever. Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday [Lect. Notes Comp. Sci 3113], pages 125–133, 2004.
  * [11] H. Jürgensen.  Synchronization.  Information and Computation, 206:1033–1044, 2008.
  * [12] J. Kari.  A Counter Example to a Conjecture Concerning Synchronizing Word in Finite Automata.  EATCS Bulletin, 73:146–147, 2001.
  * [13] J. Kari.  Synchronizing Finite Automata on Eulerian Digraphs.  Theoretical Computer Science, 295:223–232, 2003.
  * [14] H. Don M. de Bondt and H. Zantema.  Lower bounds for synchronizing word lengths in partial automata.  International Journal of Foundations of Computer Science, 30:29–60, 2019.
  * [15] P. Martyugin.  Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata.  Theory Comput Syst, 54:293–304, 2014.  doi:10.1007/s00224-013-9516-6.
  * [16] P.V. Martyugin.  A Lower Bound for the Length of the Shortest Carefully Synchronizing Words.  Russian Mathematics, 54:46–54, 2010.
  * [17] P.V. Martyugin.  Careful Synchronization of Partial Automata with Restricted Alphabets.  Computer Science – Theory and Applications. CSR 2013. Lecture Notes in Computer Science, 7913, 2013.
  * [18] B. K. Natarajan.  An Algorithmic Approach to the Automated Design of Parts Orienters.  Foundations of Computer Science, 27th Annual Symposium on, pages 132–142, 1986.
  * [19] J. E. Pin.  On Two Combinatorial Problems Arising from Automata Theory.  Proceedings of the International Colloquium on Graph Theory and Combinatorics, 75:535–548, 1983.
  * [20] I. K. Rystsov.  Asymptotic Estimate of the Length of a Diagnostic Word for a Finite Automaton.  Cybernetics, 16:194–198, 1980.
  * [21] I. K. Rystsov.  Reset Words for Commutative and Solvable Automata.  Theoretical Computer Science, 172:273–279, 1997.
  * [22] S. Sandberg.  Homing and Synchronizing Sequences.  Model-Based Testing of Reactive Systems, 3472:5–33, 2005.
  * [23] Benjamin Steinberg.  The Černý conjecture for one-cluster automata with prime length cycle.  Theoretical Computer Science, 412(39):5487–5491, 2011.
  * [24] M. Szykuła.  Improving the Upper Bound on the Length of the Shortest Reset Word.  STACS 2018, pages 56:1–56:13, 2018.
  * [25] A. Trahtman.  The Černý Conjecture for Aperiodic Automata.  Discrete Math. Theor. Comput. Sci., 9:3–10, 2007.
  * [26] J. Černý.  Poznámka k homogénnym eksperimentom s konečnými automatami.  Mat.-Fyz. Cas. Slovens.Akad. Vied., 14:208–216, 1964.
  * [27] M. Volkov.  Synchronizing Automata and the Černý Conjecture.  Language and Automata Theory and Applications, 5196:11–27, 2008\.
  * [28] M. Volkov.  Slowly Synchronizing Automata with Idempotent Letters of Low Rank.  Journal of Automata, Languages and Combinatorics, 24:375–386, 2019\.
  * [29] V. Vorel.  Subset synchronization and careful synchronization of binary finite automata.  Jour. Found. Comput. Sci., 27:557–578, 2016.
  * [30] S. Ivan Z. Gazdag and J. Nagy-Gyorgy.  Improved Upper Bounds on Synchronizing Nondeterministic Automata.  Information Processing Letters, 109:986–990, 2009.