Institute of Computer Science, University of Wrocław, Wrocław,
<EMAIL_ADDRESS>Institute of Computer Science, University
of Wrocław, Wrocław<EMAIL_ADDRESS>Robert Ferens and Marek Szykuła
[100]Theory of computation Formal languages and automata theory
[100]Mathematics of computing Discrete mathematics Combinatorics

###### Acknowledgements.

John Q. Open and Joan R. Access 2 42nd Conference on Very Important Topics
(CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United
Kingdom 42 23

# Completely Reachable Automata: A Polynomial Solution and Quadratic Bounds
for the Subset Reachability Problem

Robert Ferens  Marek Szykuła

###### Abstract

A deterministic finite automaton (DFA) with a set of states $Q$ is _completely
reachable_ if every non-empty subset of $Q$ is the image of the action of some
word applied to $Q$. The concept was first introduced by Bondar and Volkov
(2016), who also raised the question of the complexity of deciding if an
automaton is completely reachable. We develop a polynomial-time algorithm for
this problem, which is based on a complement-intersecting technique for
finding an extending word for a subset of states. Additionally, we prove a
weak Don’s conjecture for this class of automata: a subset of size $k$ is
reachable with a word of length at most $2(|Q|-k)|Q|$. This implies a
quadratic upper bound in $|Q|$ on the length of the shortest synchronizing
words (reset threshold) and generalizes earlier upper bounds derived for
subclasses of completely reachable automata.

###### keywords:

Černý conjecture, complete reachability, DFA, reachability, reset threshold,
reset word, simple idempotent, synchronizing automaton, synchronizing word,
transition semigroup

###### category:

##  1 Introduction

The concept of completely reachable automata origins from synchronizing
automata. A deterministic finite automaton is _synchronizing_ if starting from
the set of all states, after reading a suitable _reset_ word, we can narrow
the set of possible states to a singleton. On the other hand, an automaton is
_completely reachable_ if starting from the set of all states, we can reach
its every non-empty subset of states. Thus, every completely reachable
automaton is synchronizing, and the class of completely reachable automata
forms a remarkable subclass of (synchronizing) automata.

Synchronizing automata are most famous due to the longstanding open problem:
the Černý conjecture, which states that a synchronizing $n$-state automaton
admits a reset word of length at most $(n-1)^{2}$. The currently best upper
bound is cubic [13, 15, 16].

The concept of complete reachability was introduced in 2016 by Bodnar and
Volkov [4], who asked about the complexity of the computational problem of
deciding whether a given automaton is completely reachable. Later studies
revealed a connection to the so-called Rystsov graph, whose generalization is
used to characterize completely reachable automata [3, 5]. However, this does
not yet lead to an effective algorithm, as it is unknown how to compute these
graphs. Recently, the case of binary automata was solved with a quasilinear-
time algorithm [6], which strongly relies on the specificity of both letters
if they ensure the complete reachability of the automaton. Other studies
include connections with the properties of its syntactic semigroup [3, 12].

The class of completely reachable automata is not as small as it might look
so. In particular, it contains the Černý automata [7] and some other from the
so-called _slowly synchronizing series_ [1], automata with the full transition
monoid [10], and synchronizing automata with simple idempotents [14]. For
these subclasses, quadratic upper bounds instead of a cubic one were
established for the Černý ’s synchronization problem. However, for the whole
class of completely reachable automata, only cubic bounds were known (though
better than in the general case) [3].

In connection to the bounds, a remarkable conjecture and a generalization of
the Černý one is Don’s conjecture [8, Conjecture 18], which states that for an
$n$-state automaton, if a subset of states of size $1\leq k<n$ is reachable,
then it can be reached with a word of length at most $n(n-k)$. This conjecture
was disproved in general [11] but weaker versions were proposed: restricting
to completely reachable automata [11, Problem 4] and another, in relation to
avoiding words [9, Conjecture 15].

###  1.1 Contribution

We design a polynomial-time algorithm for the problem of deciding whether an
automaton is completely reachable, thus solving the 6-year-old open question
[4]. For this solution, we develop a complement-intersecting technique, which
allows finding a (short) extending word for a given subset of states (i.e.,
the preimage is larger).

Based on the discovered properties, we also prove that every non-empty subset
of $k<n$ states in a completely reachable $n$-state automaton is reachable
with a word of length smaller than $2n(n-k)$. This is a weaker version (by the
factor $2$) of Don’s conjecture stated for completely reachable automata [11,
Problem 4].

It follows that a completely reachable $n$-state automaton has a reset word of
length at most $2n^{2}-n\ln n-4n+2$ (for $n\geq 3$). This generalizes and
slightly improves the previous bounds obtained for proper subclasses of
completely reachable automata: automata with the full transition monoid (with
the previous upper bound $2n^{2}-6n+5$) [10] and synchronizing automata with
simple idempotents (with the previous upper bound $2n^{2}-4n+2$) [14].

##  2 Solving Complete Reachability in Polynomial Time

###  2.1 Reachability

A _deterministic finite complete semi-automaton_ (called simply _automaton_)
is a $3$-tuple $(Q,\Sigma,\delta)$, where $Q$ is a finite set of _states_ ,
$\Sigma$ is an _input alphabet_ , and $\delta\colon Q\times\Sigma\to Q$ is the
_transition function_ , which is extended to a function $Q\times\Sigma^{*}\to
Q$ in the usual way. Throughout the paper, by $n$ we always denote the number
of states in $Q$.

Given a subset $S\subseteq Q$, the _image_ of $S$ under the action of a word
$w\in\Sigma^{*}$ is $\delta(S,w)=\\{\delta(q,w)\mid q\in S\\}$. The _preimage_
of $S$ under the action of $w$ is $\delta^{-1}(S,w)=\\{q\in
Q\mid\delta(q,w)\in S\\}$. For a state $q$, we also write
$\delta^{-1}(q,w)=\delta^{-1}(\\{q\\},w)$. Note that $q\in S=\delta(Q,w)$ if
and only if $\delta^{-1}(q,w)\neq\emptyset$.

For a subset $S\subseteq Q$, by $\overline{S}$ we denote its complement
$Q\setminus S$.

For two subsets $S,T\subseteq Q$, if there exists a word $w\in\Sigma^{*}$ such
that $\delta(T,w)=S$ then we say that $S$ is _reachable from_ $T$ _with_ $w$.
Then we also say that $T$ is a _$w$ -predecessor_ of $S$. It is simply a
_predecessor_ of $S$ if it is a $w$-predecessor for some word $w$. There can
be many $w$-predecessors of one set, but there is at most one maximal with
respect to inclusion (and size).

######  Remark 2.1.

For $S\subseteq Q$ and $w\in\Sigma^{*}$, the preimage $\delta^{-1}(S,w)$ is a
$w$-predecessor of $S$ if and only if $\delta^{-1}(q,w)\neq\emptyset$ for
every state $q\in S$. Equivalently, we have $\delta(\delta^{-1}(S,w))=w$.

######  Remark 2.2.

For $S\subseteq Q$ and $w\in\Sigma^{*}$, if $\delta^{-1}(S,w)$ is a
$w$-predecessor of $S$, then all $w$-predecessors of $S$ are contained in it,
thus $\delta^{-1}(S,w)$ is maximal in terms of inclusion and size. If
$\delta^{-1}(S,w)$ is not a $w$-predecessor of $S$, then $S$ does not have any
$w$-predecessors.

A word $w$ is called _extending_ a subset $S$ if $|\delta^{-1}(S,w)|>|S|$ (cf.
a study on the related problems [2]). It is called _properly extending_ if
additionally $\delta^{-1}(S,w)$ is a $w$-predecessor of $S$, i.e.,
$\delta^{-1}(q,w)\neq\emptyset$ for all $q\in S$.

We say simply that a subset $S\subseteq Q$ is _reachable_ in the automaton if
$S$ is reachable from $Q$ (with any word). An automaton is _completely
reachable_ if all non-empty subsets $S\subseteq Q$ are reachable.
Equivalently, $Q$ is a predecessor of all its non-empty subsets. This gives an
alternative direct characterization of completely reachable automata:

######  Remark 2.3.

An automaton $(Q,\Sigma,\delta)$ is completely reachable if and only if for
every non-empty proper subset of $Q$ there is a properly extending word.

The decision problem Completely Reachable is the following: Given an automaton
$(Q,\Sigma,\delta)$, is it completely reachable?

###  2.2 Witnesses

For an automaton $(Q,\Sigma,\delta)$, we consider unreachable sets that have
the maximal size of all unreachable subsets of $Q$. They play the role of
witnesses (counterexamples) for the non-complete reachability of an automaton.

######  Definition 2.4 (Witness).

A non-empty set $S\subsetneq Q$ is a _witness_ if it is unreachable and has
the maximal size of all unreachable subsets of $Q$.

Since $Q$ is trivially reachable, the maximal size of unreachable subsets of
$Q$ is in $\\{0,\ldots,n-1\\}$. It equals $0$ (there is no witness) if and
only if the automaton is completely reachable.

Although any non-empty unreachable set is evidence that the automaton is not
completely reachable, it turns out that verifying if a set is a witness is
computationally easier – we show later that we can verify this and also find a
witness in polynomial time. Verifying whether a given set is reachable (or
unreachable) in general is PSPACE-complete [4].

We start with a simpler solution in co-NP, where we just guess a candidate for
a witness and verify it. Then we describe suitable modifications to work in
deterministic polynomial time, where we also compute and check all potential
candidates for a witness.

A witness obviously cannot have a larger predecessor, as this predecessor or
some other larger set would be a witness instead. Still, a set can have
exponentially many predecessors of the same size. The following observation
allows us to infer the existence of a larger predecessor indirectly.

######  Lemma 2.5.

Let $S,T\subseteq Q$ be distinct. If a word $u\in\Sigma^{*}$ is properly
extending $S\cup T$, then $u$ is also properly extending either $S$ or $T$.

######  Proof 2.6.

Let $u$ be a properly extending word for $U=S\cup T\subsetneq Q$, thus
$\delta(U^{\prime},u)=U$, $\delta^{-1}(U,u)=U^{\prime}$, and
$|U^{\prime}|>|U|$. By Remark 2.1, we have $|\delta^{-1}(q,u)|\geq 1$ for all
$q\in U$. As this holds for all the states of $S$ and $T$, they also have
their $u$-predecessors $\delta^{-1}(S,u)$ and $\delta^{-1}(T,u)$,
respectively. Suppose that $|\delta^{-1}(S,u)|=|S|$ and
$|\delta^{-1}(T,u)|=|T|$. Then $|\delta^{-1}(q,u)|=1$ for all $q\in U$, which
gives a contradiction with $|U^{\prime}|>|U|$.

######  Corollary 2.7.

Let $S,T\subsetneq Q$ be two distinct witnesses. Then $S\cup T=Q$.

######  Proof 2.8.

Since $S\neq T$, the union $S\cup T$ is larger than the witness size
$|S|=|T|$, thus it must be reachable. If $S\cup T\neq Q$, then $S\cup T$ has a
larger predecessor. By Lemma 2.5, either $S$ or $T$ also has a larger
predecessor, which contradicts that they are witnesses.

We can now focus on detecting sets that are potential witnesses. We relax a
bit the required property for being a witness and introduce an auxiliary
definition:

######  Definition 2.9 (Witness candidate).

A non-empty set $S\subsetneq Q$ is a _witness candidate_ if it does not have a
larger predecessor and all its predecessors (which are of the same size) have
pairwise disjoint complements.

Every witness is a witness candidate, and clearly, every witness candidate is
unreachable (moreover, it is unreachable from any larger set). However, both
converses do not necessarily hold.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q_{5}$$b$$b$$b$$b$$b$$b$$a$$a$$a$$a$$a$$a$
Figure 1: An example of a not completely reachable automaton ($a$’s
transitions are solid, $b$’s transitions are dashed).

######  Example 2.10.

The automaton from Figure 1 is not completely reachable.

  * •

Every set of size $5$ is reachable; e.g.,
$\delta(Q,ab)=Q\setminus\\{q_{0}\\}$.

  * •

Witnesses have size $4$ and they are: $Q\setminus\\{q_{i},q_{(i+3)\bmod 6}\\}$
for $i\in\\{0,1,2\\}$.

  * •

The sets $\\{q_{i},q_{(i+3)\bmod 6}\\}$ for $i\in\\{0,1,2\\}$ are witness
candidates but not witnesses, as they have size $2$.

  * •

The sets $\\{q_{i},q_{(i+1)\bmod 6},q_{(i+2)\bmod 6}\\}$ for $i\in\\{0,1,2\\}$
are reachable.

  * •

Singletons are unreachable, but they have a larger predecessor, e.g.,
$\delta^{-1}(\\{q_{0}\\},ab^{4})=\\{q_{2},q_{5}\\}$; so they are not witness
candidates.

  * •

If we add a letter $c$ such that $\delta(Q,c)=\\{q_{0}\\}$, then singletons
will be reachable and every proper subset of $Q$ will admit an extending word.
But witnesses and witness candidates will remain the same, as these extending
words will not be properly extending.

######  Lemma 2.11.

A witness is a witness candidate.

######  Proof 2.12.

Let $S$ be a witness and let $T$ and $T^{\prime}$ be two distinct predecessors
of $S$. As they are of the same size $|T|=|T^{\prime}|=|S|$ and $S$ is
reachable from both of the predecessors, they are also witnesses. Note that
$\overline{T}\cap\overline{T^{\prime}}=\emptyset$ is equivalent to $T\cup
T^{\prime}=Q$. Therefore, by Lemma 2.5, we must have
$\overline{T}\cap\overline{T^{\prime}}=\emptyset$, thus $S$ is a witness
candidate.

We note that the second condition in 2.9 is necessary, since then verifying
whether a set is a witness candidate can be done efficiently. Although for
determining that an automaton is not completely reachable, it would be enough
to find a set without a larger predecessor, checking this condition in general
is PSPACE-complete111A proof will be added in a next revision of this paper..

###  2.3 An Algorithm in co-NP

We can now develop a polynomial procedure that checks whether a given set $S$
is a witness candidate. The verification function is shown in 1. Starting from
$S$, we process all its predecessors in a breath-first search manner; for
this, a queue $\mathit{Process}$ is used. A next predecessor $T$ is taken in
line 6. Then, we check whether $T$ is larger than $S$, which directly implies
that $S$ is not a witness candidate. The second check in line 9 verifies
whether $\overline{T}\cap\overline{T^{\prime}}\neq\emptyset$, for some
previously processed set $T^{\prime}$. For this, we maintain $\mathit{Absent}$
array, which for every state $q$ indicates whether $q$ occurred in the
complement of some previously processed set, and if so, this set is stored in
$\mathit{Absent}[q]$. We also use this to check whether the same set $T$ has
not been processed previously (line 11), which is possible through different
words. When all predecessors of $S$ were considered and neither of the two
conditions occurred, the function reports that $S$ is a witness candidate.

Algorithm 1 Verifying whether a given subset is a witness candidate from 2.9.

1:An $n$-state automaton $\mathrsfs{A}=(Q,\Sigma,\delta)$ and a non-empty
$S\subsetneq Q$.

2:true if $S$ is a witness candidate; false otherwise.

3:function IsWitnessCandidate($\mathrsfs{A},S$)

4: $\mathit{Process}\leftarrow\textsc{EmptyFifoQueue}()$ $\triangleright$ It
contains predecessors of $S$ to be processed

5: $\mathit{Process}.\textsc{Push}(S)$

6: $\mathit{Absent}\leftarrow$ Array indexed by $q\in Q$ initialized with none

7: while not $\mathit{Process}.\textsc{Empty}()$ do

8: $T\leftarrow\mathit{Process}.\textsc{Pop}()$

9: if $|T|>|S|$ then

10: return false $\triangleright$ $T$ is a larger predecessor of $S$

11: if $\mathit{Absent}[q]\neq\textbf{none}$ for some $q\in\overline{T}$ then
$\triangleright$ Then $T\cup T^{\prime}\neq Q$

12: $T^{\prime}\leftarrow\mathit{Absent}[q]$

13: if $T=T^{\prime}$ then

14: continue$\triangleright$ $T$ has been processed previously

15: return false $\triangleright$ $T$ or $T^{\prime}$ has a larger predecessor
by Lemma 2.5

16: for all $q\in\overline{T}$ do

17: $\mathit{Absent}[q]\leftarrow T$ $\triangleright$ We know that
$\mathit{Absent}[q]$ was none

18: for all $a\in\Sigma$ do

19: if $\delta^{-1}(T,a)$ is $a$-predecessor of $T$ then

20: $\mathit{Process}$.Push($\delta^{-1}(T,a)$)

21: return true $\triangleright$ All predecessors of $S$ were checked

######  Lemma 2.13.

Function IsWitnessCandidate from 1 is correct and works in
$\mathcal{O}(n^{2}\cdot|\Sigma|)$ time.

######  Proof 2.14.

The function ends in line 8, 13, or 19. The first case with $|T|>|S|$ is
straightforward, as a witness candidate cannot have a larger predecessor. The
second case is that there is some $q\in\overline{T}\cap\overline{T^{\prime}}$,
where $T^{\prime}=\mathit{Absent}[q]$ was processed previously and $T\neq
T^{\prime}$. Again $\overline{T}\cap\overline{T^{\prime}}\neq\emptyset$
implies that $S$ is not a witness candidate.

The function ends positively (in line 19) when there are no more predecessors
of $S$ to consider ($\mathit{Process}$ becomes empty). As we checked all
predecessors of $S$, they satisfy the conditions from 1.

Finally, we bound the running time. The number of processed predecessors
(including $S$ itself) of the same size $|S|<n$ with pairwise disjoint
complements is at most $\lfloor n/(n-|S|)\rfloor$. This bounds the number of
iterations of the main loop (line 5); there may be one additional iteration at
the end with $T$ violating a condition for a witness candidate. One iteration
takes $\mathcal{O}(n\cdot|\Sigma|)$ time: lines 6–13 trivially take
$\mathcal{O}(n)$ time, updating $\mathit{Absent}$ in lines 14–15 also takes
$\mathcal{O}(n)$ time if we store a pointer/reference to $T$, and computing
direct (i.e., one-letter) predecessors in lines 13–15 takes
$\mathcal{O}(n\cdot|\Sigma|)$ time. Therefore, the function works in
$O(n^{2}\cdot|\Sigma|/(n-|S|)$ time.

######  Theorem 2.15.

Problem Completely Reachable can be solved in co-NP.

######  Proof 2.16.

We guess some witness – a non-empty subset $S\subsetneq Q$ and call
$\textsc{IsWitnessCandidate}(\mathrsfs{A},S)$. The algorithm returns the
negated answer of the function.

If the automaton is not completely reachable, then there exists some witness.
The function returns true for it, so the algorithm can guess the witness and
answer negatively. Conversely, if the automaton is completely reachable, then
there are no unreachable non-empty sets and thus no witness candidates. For
every non-empty $S\subsetneq Q$, the function returns false, so the algorithm
must answer positively.

###  2.4 A Polynomial-Time Algorithm

The overall idea is as follows. We replace guessing a witness with a
constructive procedure. We expand the function from 1 so that it not just
returns a Boolean answer but also finds a properly extending word for $S$ if
it exists. This works under a certain assumption for larger sets. Then, the
function is used to hunt for a witness, starting from all the sets of size
$n-1$ and reducing them iteratively in such a way that a witness will be found
if it exists.

####  2.4.1 Finding Properly Extending Words

Algorithm 2 An algorithm finding a properly extending word (a larger
predecessor) for a given set.

1:An $n$-state automaton $\mathrsfs{A}=(Q,\Sigma,\delta)$ and a non-empty
$S\subsetneq Q$.

2:A properly extending word $w$ of $S$ if it exists, or none if $S$ is a
witness candidate.

3:[Assumption 1] All $S^{\prime}\subsetneq Q$ such that $|S|<|S^{\prime}|<n$
have a larger predecessor.

4:function FindProperlyExtendingWord($\mathrsfs{A},S$)

5: $\mathit{Process}\leftarrow\textsc{EmptyFifoQueue}()$ $\triangleright$ It
contains pairs $(T,w)$ such that $\delta(T,w)=S$

6: $\mathit{Process}.\textsc{Push}((S,\varepsilon))$

7: $\mathit{Absent}\leftarrow\text{Array indexed by $q\in Q$ initialized with
{none}}$

8: while not $\mathit{Process}.\textsc{Empty}()$ do

9: $(T,w)\leftarrow\mathit{Process}.\textsc{Pop}()$

10: if $|T|>|S|$ then

11: return $w$ $\triangleright$ $T$ is a larger predecessor of $S$

12: if $\mathit{Absent}[q]\neq\textbf{none}$ for some $q\in\overline{T}$ then
$\triangleright$ Then $T\cup T^{\prime}\neq Q$

13: $(T^{\prime},w^{\prime})\leftarrow\mathit{Absent}[q]$

14: if $T^{\prime}=T$ then

15: continue$\triangleright$ $T^{\prime}$ has been processed previously

16: $u\leftarrow\textsc{FindProperlyExtendingWord}(\mathrsfs{A},T\cup
T^{\prime})$

17: assert($u\neq\textbf{none}$) $\triangleright$ We know this from Assumption
1

18: if $|\delta^{-1}(T,u)|>|T|$ then

19: return $uw$ $\triangleright$ $T$ has a larger predecessor

20: else

21: return $uw^{\prime}$ $\triangleright$ $T^{\prime}$ has a larger
predecessor

22: for all $q\in\overline{T}$ do

23: $\mathit{Absent}[q]\leftarrow(T,w)$ $\triangleright$ We know that
$\mathit{Absent}[q]$ was none

24: for all $a\in\Sigma$ do

25: if $\delta^{-1}(T,a)$ is $a$-predecessor of $T$ then

26: $\mathit{Process}$.Push(($\delta^{-1}(T,a),aw$))

27: return none $\triangleright$ $S$ is a witness candidate

The function is shown in 2. Similarly to IsWitnessCandidate, it verifies
whether $S$ is a witness candidate, but if not, it additionally finds a
properly extending word for $S$. Now, together with predecessor sets $T$ of
$S$, we also keep track of the words $w$ such that $\delta(T,w)=S$. The main
difference with IsWitnessCandidate is the case in line 9. For the union $T\cup
T^{\prime}$, we aim at finding a properly extending word for it, which then
turns out to be properly extending either for $T$ or $T^{\prime}$; this is
done by a recursive call in line 13. This call could fail in general, when
$T\cup T^{\prime}$ or some larger superset is a witness candidate. Hence, the
function requires _Assumption 1_ , which excludes this possibility: all
subsets larger than $|S|$ have a larger predecessor, except for $Q$. Recall
that Assumption 1 is necessary, as without it, the problem of finding a
properly extending word is PSPACE-hard.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q_{5}$$q_{6}$$q_{7}$$q_{8}$$q_{9}$$q_{10}$$q_{11}$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$
Figure 2: An example of a binary completely reachable automaton [6, Fig. 3]
($a$’s transitions are solid, $b$’s transitions are dashed).

######  Example 2.17.

Consider the automaton from Figure 2; this is the example of a completely
reachable binary automaton from [6, Fig. 3].

Let $S=\\{q_{0},q_{10}\\}$. The execution of
$\textsc{FindProperlyExtendingWord}($) is summarized as follows:

$\begin{array}[]{l|l|l|l|l}\text{Depth}&\text{Set}&\text{Found
word}&\text{Found set}&\text{Result}\\\ \hline\cr
1&\\{q_{0},q_{10}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{10}\\}}\cup\\{q_{9},q_{11}\\}&ab^{2}\\\
2&\\{q_{0},q_{9},q_{10},q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{9},q_{10},q_{11}\\}}\cup\\{q_{8},\ldots,q_{11}\\}&ab^{2}\\\
3&\\{q_{0},q_{8},\ldots,q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{8},\ldots,q_{11}\\}}\cup\\{q_{7},\ldots,q_{11}\\}&ab^{2}\\\
4&\\{q_{0},q_{7},\ldots,q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{7},\ldots,q_{11}\\}}\cup\\{q_{6},\ldots,q_{11}\\}&ab^{2}\\\
5&\\{q_{0},q_{6},\ldots,q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{6},\ldots,q_{11}\\}}\cup\\{q_{5},\ldots,q_{11}\\}&ab^{2}\\\
6&\\{q_{0},q_{5},\ldots,q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{5},\ldots,q_{11}\\}}\cup\\{q_{4},\ldots,q_{11}\\}&ab^{2}\\\
7&\\{q_{0},q_{4},\ldots,q_{11}\\}&\underline{\varepsilon}\text{ or
}b&\underline{\\{q_{0},q_{4},\ldots,q_{11}\\}}\cup\\{q_{3},\ldots,q_{11}\\}&ab^{2}\\\
8&\\{q_{0},q_{3},\ldots,q_{11}\\}&\varepsilon\text{ or
}\underline{b}&\\{q_{0},q_{3},\ldots,q_{11}\\}\cup\underline{\\{q_{2},\ldots,q_{11}\\}}&ab^{2}\\\
9&Q\setminus\\{q_{1}\\}&ab&Q&ab\\\ \end{array}$

_Depth_ denotes the number of the recursive call. _Set_ is the input set $S$
for this call. _Found word_ is either two words or one word, depending on
which case occurs. _Found set_ is either the union of two sets or a larger
predecessor; in any case, it is larger than the input set. _Result_ is the
returned properly extending word, which is either constructed from the
recursive call or is known directly. The underlined results are those chosen
for constructing the final word.

The function works as follows: $S=\\{q_{0},q_{10}\\}$ does not have a
$a$-predecessor, because $\delta^{-1}(q_{0},a)$ is empty, but it has the
$b$-predecessor $\delta^{-1}(\\{q_{0},q_{10}\\},b)=\\{q_{9},{11}\\}$. The
complements of $\\{q_{0},q_{10}\\}$ and $\\{q_{9},q_{11}\\}$ are not disjoint,
thus there is a recursive call for the union
$\\{q_{0},q_{9},q_{10},q_{11}\\}$. This is repeated $7$ times, when the states
$q_{8},\ldots,q_{2}$ are subsequently added one by one. Finally, we get the
set $Q\setminus\\{q_{1}\\}$. Its $b$-predecessor $Q\setminus\\{q_{0}\\}$ is
processed and has a disjoint complement with $Q\setminus\\{q_{1}\\}$. Then,
$\delta^{-1}(Q\setminus\\{q_{0}\\},a)=Q$, thus a larger predecessor is found.
Now, the returned word is constructed from the recursive calls. Word $ab$
found in the last call is properly extending both sets
$\\{q_{0},q3,\ldots,q_{11}\\}$ and $Q\setminus\\{q_{0},q_{1}\\}$. Here the
function uses the latter, but both choices would work. Thus, the word $ab^{2}$
is properly extending for $\\{q_{0},q_{3},\ldots,q_{1}1\\}$. It turns out that
in all the previous calls, $ab^{2}$ is properly extending for the input set,
thus the word is not prolonged.

######  Lemma 2.18.

Function FindProperlyExtendingWord is correct and works in
$\mathcal{O}(n^{2}\log n\cdot|\Sigma|)$ time. Moreover, the returned word has
length $\mathcal{O}(n\log n)$.

######  Proof 2.19.

The case where $S$ is a witness candidate follows in the same way as for
$\textsc{IsWitnessCandidate}($) (in the proof of Lemma 2.13). The function
checks all its predecessors and returns none in line 24.

Consider a set $S$ that is not a witness candidate. Then necessarily, the
function ends in line 8, line 16, or line 18. In line 8, a larger predecessor
is found directly thus the answer is correct. So suppose that the condition in
line 9 holds. The recursive call in line 13 returns a word $u$ that is
properly extending $T\cup T^{\prime}\subsetneq Q$; this follows by induction
on the set size, assuming that FindProperlyExtendingWord is correct for larger
sets than $S$. By Lemma 2.5, $u$ is properly extending either $T$ or
$T^{\prime}$. The function directly checks the first case in line 15, and the
second case must hold otherwise. Therefore, the returned word is properly
extending $S$.

Concerning the running time, one call of the function does at most $\lceil
n/(n-|S|)\rceil$ iterations (including the last one with returning the
result). An iteration takes $\mathcal{O}(n\cdot|\Sigma|)$ time if we do not
copy words directly but operate with pointers (for concatenation) and maintain
the induced transformations. These give
$\mathcal{O}(n^{2}\cdot|\Sigma|/(n-|S|))$ time. There are also recursive calls
for larger subsets. In the worst case, each time the union subset is larger by
$1$, so by summing the running time from all the calls, we obtain:

$\sum_{k=|S|}^{n-1}\mathcal{O}(n^{2}\cdot|\Sigma|/(n-k))\leq\mathcal{O}(n^{2}\cdot|\Sigma|\cdot
H_{n-|S|})\leq\mathcal{O}(n^{2}\log n\cdot|\Sigma|),$

where $H_{i}$ is the $i$-th harmonic number
($H_{i}=1+\frac{1}{2}+\ldots+\frac{1}{i}\leq\ln{(i)}+1$ is a well-known
inequality).

To bound the length of the found word, it is enough to sum the upper bounds on
the number of iterations (as each iteration increments the processed word by
at most one letter) in all recursive calls:

$\sum_{k=|S|}^{n-1}\lceil n/(n-k)\rceil\leq
nH_{n-|S|}+(n-|S|)\leq\mathcal{O}(n\log n).$

####  2.4.2 Reduction

Suppose that given a set $S\subsetneq Q$, we search for a witness that is
contained within it. Having a properly extending word $w$ for $S$, we can
reduce $S$ to its proper subset by excluding some states which surely cannot
be in any witness contained in $S$. The next lemma shows the criterion, which
is realized by $\textsc{Reduce}(\mathrsfs{A},S,w)$ in 3.

######  Lemma 2.20.

Let $S\subseteq Q$ and $\delta^{-1}(S,w)$ be a $w$-predecessor of $S$ for some
$w$. Then for every witness $S^{\prime}\subseteq S$, every state $q\in
S^{\prime}$ is such that $|\delta^{-1}(q,w)|=1$.

######  Proof 2.21.

Since $\delta^{-1}(S,w)$ is a $w$-predecessor of $S$, by Remark 2.1, we have
$\delta^{-1}(q,w)\neq\emptyset$ for every state $q\in S$. Suppose for a
contradiction that there exists $S^{\prime}\subseteq S$ that is a witness and
contains a state $p\in S^{\prime}$ such that $|\delta^{-1}(p,w)|>1$. Let
$T^{\prime}=\delta^{-1}(S^{\prime},w)$. Since $\delta^{-1}(q,w)\neq\emptyset$
for all $q\in S^{\prime}$, $T^{\prime}$ is a $w$-predecessor of $S^{\prime}$.
Because $|\delta^{-1}(p,w)|>1$, we have $|T^{\prime}|>|S^{\prime}|$, so
$T^{\prime}$ must be reachable as it is larger than the witness $S^{\prime}$.
But then also $S^{\prime}$ is reachable through $T^{\prime}$, contradicting
the property of $S^{\prime}$.

Algorithm 3 Reducing a set for possible witness containment.

1:An $n$-state automaton $\mathrsfs{A}=(Q,\Sigma,\delta)$, a non-empty
$S\subsetneq Q$, and a properly extending word $w$ for $S$.

2:A proper subset $S^{\prime}\subsetneq S$ that contains all the witnesses in
$S$.

3:function Reduce($\mathrsfs{A}$, $S$, $w$)

4: return $\\{q\in S\colon|\delta^{-1}(q,w)|=1\\}$

####  2.4.3 Finding a Witness

Algorithm 4 A polynomial-time algorithm verifying the complete reachability of
an automaton or finding a witness.

1:An $n$-state automaton $\mathrsfs{A}=(Q,\Sigma,\delta)$.

2:none if $\mathrsfs{A}$ is completely reachable; a witness otherwise.

3:function FindWitness($\mathrsfs{A}$)

4: $\mathit{Queue}\leftarrow\textsc{EmptyPriorityQueue}()$ $\triangleright$
Ordered by set size; the largest sets go first

5: for all $q\in Q$ do

6: $\mathit{Queue}.\textsc{Push}(Q\setminus\\{q\\})$

7: while $\textbf{not}\ \mathit{Queue}.\textsc{Empty}()$ do

8: $S\leftarrow\mathit{Queue}.\textsc{Pop}()$ $\triangleright$ Get a set of
the largest size

9: $w\leftarrow\textsc{FindProperlyExtendingWord}(\mathrsfs{A},S)$

10: if $w=\textbf{none}$ then

11: return $S$ $\triangleright$ Witness found

12: $S^{\prime}\leftarrow\textsc{Reduce}(\mathrsfs{A},S,w)$ $\triangleright$
$S^{\prime}\subsetneq S$

13: if $S^{\prime}\neq\emptyset$ and not
$\mathit{Queue}.\textsc{Contains}(S^{\prime})$ then

14: $\mathit{Queue}.\textsc{Push}(S^{\prime})$

15: return none $\triangleright$ No witnesses

We have all ingredients to build a polynomial algorithm that solves the
decision problem Completely Reachable. It is shown in 4. If the automaton is
not completely reachable, the algorithm also finds a witness. Starting from
all sets of size $n-1$, we process sets in the order of decreasing size.
Processing a set consists of finding a properly extending word for it and
reducing the set by this word.

######  Lemma 2.22.

Function FindWitness is correct and works in $\mathcal{O}(n^{4}\log
n\cdot|\Sigma|)$ time.

######  Proof 2.23.

First note that if there is no witness, then Assumption 1 for
FindProperlyExtendingWord is always satisfied, thus this function in line 7
always returns a word. So the algorithm will not return a witness. As the
inserted sets $S^{\prime}$ are proper subsets of $S$, all the sets are
eventually reduced to the empty set, thus the algorithm terminates and returns
none.

Suppose that there is a witness $W\subsetneq Q$. We prove by induction that
before each iteration of the main loop in line 5, $W$ is contained in one of
the sets in $\mathit{Queue}$. For the first iteration the statement holds:
since $W\neq Q$, we have $W\subseteq Q\setminus\\{q\\}$ for some $q\in Q$. It
is enough to ensure that an iteration does not break the statement. An
iteration removes only $S$ from $\mathit{Queue}$. If there is some witness
contained in the other sets from $\mathit{Queue}$, then we are done; so we
further assume that all witnesses are contained in $S$. If $S$ is a witness,
then $\textsc{FindProperlyExtendingWord}(S)$ returns none and the function
ends. If a witness is contained in $S$, then from Lemma 2.20, it is also
contained in $S^{\prime}$, which is then added to $\mathit{Queue}$.

Concerning the running time, there are at most $n(n-1)$ iterations of the main
loop: we start with $n$ sets of size $n-1$, and they are reduced by at least
one up to the empty set. The call to FindProperlyExtendingWord in an iteration
takes at most $\mathcal{O}(n^{2}\log n\cdot|\Sigma|)$ time (Lemma 2.18); the
other operations take no more than $\mathcal{O}(n^{2})$ with a native
implementation. Altogether, we have $\mathcal{O}(n^{4}\log n\cdot|\Sigma|)$.

######  Remark 2.24.

The number of witnesses of size $k$ is at most $\lfloor n/k\rfloor$, as their
complements must be pairwise disjoint. Function FindWitness can be easily
modified to find all the witnesses: after finding the first witness of size
$k$, we can continue the main loop in line 5 until all sets of size $k$ are
processed.

##  3 An Upper Bound on Reset Threshold

###  3.1 Synchronization

A _reset word_ is a word $w$ such that $|\delta(Q,w)|=1$. Equivalently, we
have $\delta^{-1}(q,w)=Q$ for some $q\in Q$. If an automaton admits a reset
word, then it is called _synchronizing_ and its _reset threshold_ is the
length of the shortest reset words.

The central problem in the theory of synchronizing automata is the famous
Černý conjecture, which states that every synchronizing $n$-state automaton
has its reset threshold at most $(n-1)^{2}$.

Obviously, completely reachable automata are synchronizing. The previously
proposed upper bound on their reset threshold is
$7/48n^{3}+\mathcal{O}(n^{2})$ [3], which is obtained through the technique of
avoiding [16], that is, it follows in particular from the fact that every set
of size $n-1$ is reachable with a word of length at most $n$.

###  3.2 Finding Short Properly Extending Words

For a completely reachable automaton, function
$\textsc{FindProperlyExtendingWord}($) always finds a properly extending word.
Therefore, using the well-known _extension_ method (e.g., [17]), we can
construct a synchronizing word starting from some singleton $\\{q\\}$ and
iteratively increasing the set by at least one, finally obtaining $Q$. This is
an easy way to get the upper bound of order $\mathcal{O}(n^{2}\log n)$: the
length of a word returned by $\textsc{FindProperlyExtendingWord}(S)$ is upper
bounded by $\mathcal{O}(n\log n)$ (Lemma 2.18). However, we can do better.

The idea is to keep track of all subsets for an intersection of complements,
instead of starting an independent search for a properly extending word
recursively. This modification is shown in 5. The correctness follows from our
earlier arguments.

Algorithm 5 An algorithm finding a short properly extending word.

1:An $n$-state completely reachable automaton $\mathrsfs{A}=(Q,\Sigma,\delta)$
and a non-empty $S\subsetneq Q$.

2:A properly extending word $w$ of $S$.

3:function FindShortProperlyExtendingWord($\mathrsfs{A},S$)

4: $\mathit{Trace}\leftarrow\textsc{EmptyMap}()$ $\triangleright$ For a
processed set, it stores a word or two sets

5: $S^{\prime}\leftarrow S$

6: $\mathit{Process}\leftarrow\textsc{EmptyFifoQueue}()$ $\triangleright$ It
contains pairs $(T,w)$ such that $\delta(T,w)=S^{\prime}$

7: $\mathit{Process}.\textsc{Push}((S^{\prime},\varepsilon))$

8: while not $\mathit{Process}.\textsc{Empty}()$ do

9: $(T,w)\leftarrow\mathit{Process}.\textsc{Pop}()$

10: if $\mathit{Trace}[T]$ is defined then

11: continue

12: $\mathit{Trace}[T]\leftarrow w$

13: if $|T|>|S^{\prime}|$ then

14: $S^{\prime}\leftarrow T$

15: break

16: while there is $T^{\prime}$ such that $\mathit{Trace}[T^{\prime}]$ is
defined and $T\subsetneq T\cup T^{\prime}\subsetneq Q$ do

17: $U\leftarrow T\cup T^{\prime}$ $\triangleright$ $|U|>|S|$

18: $\mathit{Trace}[U]\leftarrow(T,T^{\prime})$

19: $T\leftarrow U$

20: $S^{\prime}\leftarrow U$

21: $w\leftarrow\varepsilon$ $\triangleright$ The empty word

22: $\mathit{Process}\leftarrow\textsc{EmptyFifoQueue}($) $\triangleright$
Continue only from the largest set

23: for all $a\in\Sigma$ do

24: if $\delta^{-1}(T,a)$ is $a$-predecessor of $T$ then

25: $\mathit{Process}$.Push(($\delta^{-1}(T,a),aw$))

26: $u\leftarrow\varepsilon$ $\triangleright$ The empty word

27: while $S^{\prime}\neq S$ do

28: if $\mathit{Trace}[S^{\prime}]$ is a word then

29: $w\leftarrow\mathit{Trace}[S^{\prime}]$

30: $S^{\prime}\leftarrow\delta(S^{\prime},w)$

31: $u\leftarrow uw$

32: else

33: $(T,T^{\prime})\leftarrow\mathit{Trace}[S^{\prime}]$

34: if $|\delta^{-1}(T,u)|>|T|$ then

35: $S^{\prime}\leftarrow T$

36: else

37: $S^{\prime}\leftarrow T^{\prime}$

38: return $w$

####  3.2.1 Nested Boxes

To bound the length of the found word, we consider an auxiliary combinatorial
problem.

Consider an $n$-element universe $Q$. Two subsets $S,T\subseteq Q$ are
_colliding_ if $S\cap T\notin\\{\emptyset,S,T\\}$. Thus, colliding sets have a
non-trivial intersection. A family of non-empty subsets of $Q$ is called _non-
colliding_ if all the subsets are pairwise non-colliding.

######  Definition 3.1.

For an $n\geq 1$, the number _$\mathit{MaxNestedBoxes}(n)$_ is the maximum
size of a non-colliding family for an $n$-element universe.

The problem is equivalent to, e.g., the maximum number of boxes for $n$ items,
such that a box must contain either an item or at least two boxes. Another
interpretation is the maximum number of balanced non-trivial parentheses for
an $n$-element string, where a pair is trivial if it is empty inside or
contains only one pair.

######  Lemma 3.2.

$\mathit{MaxNestedBoxes}(n)=2n-1$.

######  Proof 3.3.

It goes by induction on $n$. For the base case,
$\mathit{MaxNestedBoxes}(1)=1$.

For $n>1$, we can always take the set with all $n$ elements, and there should
be exactly two its proper subsets that are maximal with respect to inclusion.
Otherwise, if there are more, we could add a union of two of them and obtain
more sets. Thus, the problem is recursive:

$\displaystyle\mathit{MaxNestedBoxes}(n)=$ $\displaystyle\
1+\max_{p\in\\{1,\ldots,n-1\\}}(\mathit{MaxNestedBoxes}(p)+\mathit{MaxNestedBoxes}(n-p))$
$\displaystyle=$ $\displaystyle\
1+\max_{p\in\\{1,\ldots,n-1\\}}(2p-1+2(n-p)-1)$ $\displaystyle=$
$\displaystyle\ 1+\max_{p\in\\{1,\ldots,n-1\\}}(2n-2)$ $\displaystyle=$
$\displaystyle\ 1+2n-2=2n-1.$

The generalized version of the problem limits the maximum size of the subsets:

######  Definition 3.4.

For an $n\geq 1$, the number _$\mathit{MaxNestedBoxes}(n,k)$_ is the maximum
size of a non-colliding family for an $n$-element universe, where each subset
from the family has size at most $k$.

######  Lemma 3.5.

$\mathit{MaxNestedBoxes}(n,k)=2n-\lceil n/k\rceil$.

######  Proof 3.6.

We prove the equality by induction on $k$ and on $n$. The cases with $k\geq n$
are solved by Lemma 3.2. Let $k>n\geq 1$. Consider a family satisfying the
conditions for $n$ and $k$ that has size $\mathit{MaxNestedBoxes}(n,k)$.

If the largest subsets have size $k$, then we split the problem:

$\mathit{MaxNestedBoxes}(n,k)=\mathit{MaxNestedBoxes}(k)+\mathit{MaxNestedBoxes}(n-k,k)$

By Lemma 3.2 and the inductive assumption for
$\mathit{MaxNestedBoxes}(n-k,k)$:

$\mathit{MaxNestedBoxes}(k)+\mathit{MaxNestedBoxes}(n-k,k)=2k-1+2(n-k)-\lceil(n-k)/k\rceil=2n-\lceil
n/k\rceil.$

If the largest subsets have size $k^{\prime}<k$, then this means from the
inductive assumption:

$\mathit{MaxNestedBoxes}(n,k)=\mathit{MaxNestedBoxes}(n,k^{\prime})=2n-\lceil
n/k^{\prime}\rceil\leq 2n-\lceil n/k\rceil.$

Thus, the number is not larger than in the previous case, and by taking the
maximum from the two possibilities we get the claim.

####  3.2.2 Final Bounding

We apply the above combinatorial problem to upper bound the length of a word
found by FindShortProperlyExtendingWord:

######  Lemma 3.7.

For a completely reachable automaton and a non-empty proper subset
$S\subsetneq Q$, the word returned by FindShortProperlyExtendingWord from 5
has length at most $\mathit{MaxNestedBoxes}(n,n-|S|)=2n-\lceil
n/(n-|S|)\rceil$.

######  Proof 3.8.

Let $\mathcal{X}$ be the family of subsets that were defined as keys for
$\mathit{Trace}$ as the last in an iteration of the main loop in line 6 (i.e.,
defined either in line 16 or line 10 if the while condition was not
fulfilled). Let $\overline{\mathcal{X}}$ denote $\mathcal{X}$ where each
subset is replaced with its complement. Note that $\overline{\mathcal{X}}$ is
a non-colliding family; the loop in line 15 is repeated until a set
$T^{\prime}$ is found such that its complement does not collide with any
complement of a key in $\mathit{Trace}$.

The size of $\overline{\mathcal{X}}$ equals the number of iterations of the
main loop. When reconstructing the word, the sum of the lengths of words $w$
in line 28 is also upper bounded by the number of iterations.

As the family $\overline{\mathcal{X}}$ is non-colliding and the subsets have
size $\leq n-|S|$, the upper bound follows.

To provide a formula for our bounds, we will need the following auxiliary
inequality:

######  Lemma 3.9.

For $1\leq m\leq n-1$, we have:

$\sum_{k=m}^{n-1}\mathit{MaxNestedBoxes}(n,n-k)\leq(n-m)2n-n\ln(n-m)-n/(n-m).$

######  Proof 3.10.

$\displaystyle\sum_{k=m}^{n-1}\mathit{MaxNestedBoxes}(n,n-k)=$ $\displaystyle\
(n-m)2n-\sum_{k=m}^{n-1}\lceil n/(n-k)\rceil$ $\displaystyle\leq$
$\displaystyle\ (n-m)2n-\sum_{k=m}^{n-1}n/(n-k)$ $\displaystyle=$
$\displaystyle\ (n-m)2n-nH_{n-m},$

where $H_{i}$ is the $i$-th harmonic number. Using the well-known inequality
$H_{i}\geq\ln i+1/i$, we get the upper bound:

$\displaystyle(n-m)2n-nH_{n-m}\leq$ $\displaystyle\
(n-m)2n-n(\ln(n-m)+1/(n-m))$ $\displaystyle=$ $\displaystyle\
(n-m)2n-n\ln(n-m)-n/(n-m).$

Using the standard extension method, we get:

######  Theorem 3.11.

For a completely reachable $n$-state automaton $(Q,\Sigma,\delta)$, every non-
empty proper subset $S\subseteq Q$ is reachable with a word of length at most
$(n-|S|)2n-n\ln(n-|S|)-n/(n-|S|)<2n(n-|S|)$.

######  Proof 3.12.

Starting from $S$, we apply at most $n-|S|$ times a properly extending word
found by FindShortProperlyExtendingWord, which, by Lemma 3.7,is bounded by
$\mathit{MaxNestedBoxes}(n,n-k)$, where $k=|S|,\ldots,n-1$. The bound on the
sum is provided by Lemma 3.9.

######  Theorem 3.13.

The reset threshold of a completely reachable automaton with $n\geq 3$ states
is at most $(n-2)2n-n\ln(n-2)-n/(n-2)<2n^{2}-n\ln n-4n+2$.

######  Proof 3.14.

We find a state $q$ such that $|\delta^{-1}(\\{q\\},a)|\geq 2$ for some letter
$a$. Then we extend $\delta^{-1}(\\{q\\},a)$ by the word from Theorem 3.11.
Since $\ln n-\ln(n-2)\leq 2$ for $n\geq 3$, we also get the inequality.

## References

  * [1] D. S. Ananichev, M. V. Volkov, and V. V. Gusev.  Primitive digraphs with large exponents and slowly synchronizing automata.  Journal of Mathematical Sciences, 192(3):263–278, 2013.
  * [2] M. V. Berlinkov, R. Ferens, and M. Szykuła.  Preimage problems for deterministic finite automata.  Journal of Computer and System Sciences, 115:214–234, 2021.
  * [3] E. A. Bondar, D. Casas, and M. V. Volkov.  Completely reachable automata: an interplay between automata, graphs, and trees, 2022.  URL: https://arxiv.org/abs/2201.05075.
  * [4] E. A. Bondar and M. V. Volkov.  Completely Reachable Automata.  In Cezar Câmpeanu, Florin Manea, and Jeffrey Shallit, editors, DCFS, pages 1–17. Springer, 2016.
  * [5] E. A. Bondar and M. V. Volkov.  A Characterization of Completely Reachable Automata.  In Mizuho Hoshi and Shinnosuke Seki, editors, DLT, pages 145–155. Springer, 2018.
  * [6] D. Casas and M. V. Volkov.  Binary completely reachable automata.  In LATIN. Springer, 2022.  To appear; full version at https://arxiv.org/abs/2205.09404.
  * [7] J. Černý.  Poznámka k homogénnym experimentom s konečnými automatami.  Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208–216, 1964.  In Slovak.
  * [8] H. Don.  The Černý Conjecture and 1-Contracting Automata.  Electronic Journal of Combinatorics, 23(3):P3.12, 2016.
  * [9] R. Ferens, M. Szykuła, and V. Vorel.  Lower Bounds on Avoiding Thresholds.  In MFCS, volume 202 of LIPIcs, pages 46:1–46:14. Schloss Dagstuhl, 2021.
  * [10] F. Gonze, V. V. Gusev, B. Gerencser, R. M. Jungers, and M. V. Volkov.  On the interplay between Babai and Černý’s conjectures.  In DLT, volume 10396 of LNCS, pages 185–197. Springer, 2017\.
  * [11] F. Gonze and R. M. Jungers.  Hardly Reachable Subsets and Completely Reachable Automata with 1-Deficient Words.  Journal of Automata, Languages and Combinatorics, 24(2–4):321–342, 2019.
  * [12] S. Hoffmann.  Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words.  In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, LATA, LNCS, pages 305–317. Springer, 2021.
  * [13] J.-E. Pin.  On two combinatorial problems arising from automata theory.  In Proceedings of the International Colloquium on Graph Theory and Combinatorics, volume 75 of North-Holland Mathematics Studies, pages 535–548, 1983.
  * [14] I.K. Rystsov.  Estimation of the length of reset words for automata with simple idempotents.  Cybern. Syst. Anal. 36, pages 339–344, 2000.
  * [15] Y. Shitov.  An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata.  Journal of Automata, Languages and Combinatorics, 24(2–4):367–373, 2019.
  * [16] M. Szykuła.  Improving the Upper Bound on the Length of the Shortest Reset Word.  In STACS 2018, LIPIcs, pages 56:1–56:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
  * [17] M. Volkov.  Synchronizing automata and the Černý conjecture.  In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11–27. Springer, 2008.