Institute of Natural Sciences and Mathematics, Ural Federal University,
Ekaterinburg<EMAIL_ADDRESS>Institute of Computer Science,
University of Wrocław, Wrocław<EMAIL_ADDRESS>in
part by the National Science Centre, Poland under project number
2017/25/B/ST6/01920. Université Gustave Eiffel, LIGM, Marne-la-Vallée,
<EMAIL_ADDRESS>Institute of Computer Science, University of
Wrocław, Wrocław<EMAIL_ADDRESS>in part by the National
Science Centre, Poland under project number 2017/25/B/ST6/01920. Mikhail V.
Berlinkov, Robert Ferens, Andrew Ryzhikov, 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

# Synchronizing Strongly Connected Partial DFAs

Mikhail V. Berlinkov  Robert Ferens  Andrew Ryzhikov  Marek Szykuła

###### Abstract

We study synchronizing partial DFAs, which extend the classical concept of
synchronizing complete DFAs and are a special case of synchronizing
unambiguous NFAs. A partial DFA is called synchronizing if it has a word
(called a reset word) whose action brings a non-empty subset of states to a
unique state and is undefined for all other states. While in the general case
the problem of checking whether a partial DFA is synchronizing is PSPACE-
complete, we show that in the strongly connected case this problem can be
efficiently reduced to the same problem for a complete DFA. Using
combinatorial, algebraic, and formal languages methods, we develop techniques
that relate main synchronization problems for strongly connected partial DFAs
with the same problems for complete DFAs. In particular, this includes the
Černý and the rank conjectures, the problem of finding a reset word, and upper
bounds on the length of the shortest reset words of literal automata of finite
prefix codes. We conclude that solving fundamental synchronization problems is
equally hard in both models, as an essential improvement of the results for
one model implies an improvement for the other.

###### keywords:

Černý conjecture, literal automaton, partial automaton, prefix code, rank
conjecture, reset threshold, reset word, synchronizing automaton,
synchronizing word

###### category:

##  1 Introduction

Synchronization is a concept in various domains of computer science which
consists in regaining control over a system by applying (or observing) a
specific set of input instructions. These instructions are usually required to
lead the system to a fixed state no matter in which state it was at the
beginning. This idea has been studied for automata (deterministic [8, 36],
non-deterministic [17], unambiguous [2], weighted and timed [10], partially
observable [22], register [1], nested word [9]), parts orienting in
manufacturing [13, 23], testing of reactive systems [30], variable length
codes [5], and Markov Decision Processes [11, 12].

In this paper, we study the synchronization of partial DFAs, which are a
generalization of complete DFAs and a special case of unambiguous NFAs. We are
motivated by applications of this model and its connections with others, as
well as the need for new techniques applied to partial DFAs. The problems for
strongly connected partial DFAs are a motivation for further development and
generalization of the methods applied for complete DFAs, since, as we show,
these models are closely related. We also hope that our methods will serve as
a step toward studying a wider class of strongly connected unambiguous NFAs.

1.1 Observing a reactive system Consider a finite-state reactive system
modeled by a partial DFA (by partial we mean that for some states there can be
no outgoing transitions corresponding to some letters). The observer knows the
structure of the DFA but does not know its current state. At every step, the
DFA reads a letter (also known to the observer) and transits to another state.
The observer wants to eventually learn the actual state of the DFA. Since the
DFA is deterministic, once a state is known, it will be known forever.

In this setting, the actual state is known if and only if the system reads a
_reset word_ – a word which transits a non-empty set of states to a single
state and is undefined for all other states. The presence of undefined
transitions indicates that certain actions cannot be performed from certain
states, which can be essential for synchronization.

For several identical systems running in parallel and receiving the same input
(but possibly starting from different states), the presence of a reset word
guarantees that all systems end up in the same state. This idea can be used in
robotics, where a sequence of passive obstacles is used for orienting a large
number of arbitrarily rotated parts arriving simultaneously on a conveyor belt
([13, 23], see also [36] for an illustrative example).

Reactive systems (such as Web servers, communication protocols, operating
systems and processors) are systems developed to run without termination and
interact through visible events, so it is natural to assume that the system
can return to any state from any other state (NFAs with this property are
called _strongly connected_). The probabilistic version of the described
problem for strongly connected partial DFAs has been considered in the context
of $\varepsilon$-machines [34]. In particular, the observer knows the state of
an $\varepsilon$-machine precisely if and only if a reset word for the
underlying partial DFA was applied. Some experimental results on finding
shortest reset words for partial DFAs were recently presented in [31].

1.2 Synchronizing automata There exist several definitions that generalize the
notion of a synchronizing complete DFA to larger classes of NFAs. In this
subsection, we describe the notion which preserves most of the properties of
the complete DFAs case, and in 1.5 we briefly describe alternative notions.

An NFA is called _unambiguous_ if for every two states $p,q$ and every word
$w$, there is at most one path from $p$ to $q$ labeled by $w$ [2]. In the
strongly connected case, this is equivalent to a more classical definition of
an unambiguous automaton with chosen initial and final states, if there is a
unique initial state and a unique final state. An unambiguous NFA is called
_synchronizing_ if there exist two non-empty subsets $C,R$ of its states and a
word $w$ (called a _reset_ word) such that its action maps every state in $C$
exactly to the whole set $R$, and is undefined for all states outside $C$ [2].
For partial DFAs, the set $R$ has size one [5], and, for complete DFAs, the
set $C$ is also the whole set of states [36].

Partial DFAs are a natural intermediate class between unambiguous NFAs and
complete DFAs. The bounds on the length of shortest reset words in strongly
connected partial DFAs have not been studied before. The famous Černý
conjecture, which is one of the most longstanding open problems in automata
theory, states that for an $n$-state complete DFA we can always find a reset
word of length at most $(n-1)^{2}$, unless there are no reset words. The best
known upper bound is cubic in $n$ [32, 33], and the problem of deciding
whether a complete DFA is synchronizing is solvable in time quadratic in $n$
[36]. For an $n$-state strongly connected unambiguous NFA the best known upper
bound on the length of a shortest reset word is $n^{5}$, and the existence of
a reset word is verifiable in time $\mathcal{O}(n^{5})$ [28]. The same upper
bound holds for the length of the shortest mortal words in strongly connected
unambiguous NFAs [21], whereas partial DFAs admit a tight quadratic bound
[26].

1.3 Synchronizing codes A _variable length code_ $X$ (which we call a _code_)
is a set of finite words over a finite alphabet $\Sigma$, such that no word
over $\Sigma$ can be written as a concatenation of codewords of $X$ in two
different ways. Such codes (especially Huffman codes [16]) are widely used for
lossless data compression. Since the lengths of codewords can be different,
one transmission error can spoil the whole decoding process, causing a major
data loss. Also, in general, decoding a part of a message (e.g., a segment of
a compressed video stream) is not possible without decoding the whole message.

These issues can be addressed by using synchronizing codes. A code $X$ is
called _synchronizing_ if there exists a _synchronizing_ word $w\in X^{*}$
such that for every $uwv\in X^{*}$ we have $uw,wv\in X^{*}$. The occurrence of
the word $ww$ thus stops error propagation and allows parallel decoding of the
two parts of the message. More generally, each appearance of the word $ww$ in
a coded message allows running decoding independently from the position after
the first $w$.

A code is called _prefix_ if none of its codewords is a prefix of another
codeword. Such codes allow obtaining the correct partition of a message into
codewords one by one by going from left to right. Even if a code is
synchronizing, there are no guarantees that a synchronizing word will appear
in a message. Codes where every long enough concatenation of codewords is
synchronizing are called _uniformly synchronizing_ [5, 7]. A prefix code is
called _maximal_ if it is not a subset of another prefix code. All non-trivial
uniformly synchronizing finite prefix codes are non-maximal [5].

1.4 Automata for $X^{*}$ A code recognized by an NFA as a language is called
_recognizable_. In particular, every finite code is recognizable. To argue
about synchronization properties of a recognizable code $X$, special NFAs
recognizing $X^{*}$ are studied. These NFAs have a unique initial and final
state $r$ such that the set of words labeling paths from $r$ to itself
coincides with $X^{*}$, thus they are also strongly connected. Provided a
recognizable code $X$, an NFA with the described properties can be chosen to
be unambiguous [5]. Moreover, this NFA can be chosen to be a partial
(respectively, a complete) DFA if and only if $X$ is a recognizable prefix
(respectively, recognizable maximal prefix) code [5].

For such an unambiguous NFA with the properties as above, $X$ is synchronizing
if and only if the NFA is synchronizing, and the length of a shortest
synchronizing word for $X$ is at most the length of a shortest reset word of
the NFA plus twice its number of states [5, Chapter 4].

Finite prefix codes admit a direct construction of partial DFAs with the
described properties, called literal automata. Let $X$ be a finite prefix code
over an alphabet $\Sigma$. The _literal automaton_
$\mathrsfs{A}_{X}=(Q,\Sigma,\delta)$ is constructed as follows. The set of
states $Q$ is the set of all proper prefixes of the words in $X$, the
transition function is defined as follows: $\delta(q,x)=qx$ if $qx\notin X$
and $qx$ is a proper prefix of a word in $X$, $\delta(q,x)=\varepsilon$ if
$qx\in X$, and $\delta(q,x)=\bot$ otherwise. The state corresponding to the
empty prefix $\varepsilon$ is called the _root state_. The _height_ of a
literal automaton is the length of a longest path of its transitions without
repetition of states; equivalently, this is the length of the longest word in
$X$ minus one. Note that the number of states of $\mathrsfs{A}_{X}$ is at most
the total length of all codewords of $X$, which allows to directly transfer
upper bounds from literal automata to finite prefix codes. An example of a
literal automaton is shown in Fig. 1(right). The literal automaton of a prefix
code can be used as a decoder for this code by adding output labels to the
transitions [5].

1.5 Carefully synchronizing DFAs For general NFAs, synchronizability can be
generalized to D$i$-directability for $i=1,2,3$ [17]. As discussed in [38,
Section 6.3], for partial DFAs the notions of D$1$\- and D$3$-directing words
both coincide with _carefully synchronizing_ words. These are words sending
every state of a partial DFA to the same state, not using any undefined
transitions at all. A D$2$-directing word for a partial DFA is either
carefully synchronizing or mortal (undefined for every state). The definitions
of carefully synchronizing and D$2$-directing words are different from our
definition of synchronizing words.

A carefully synchronizing word can be applied to a partial DFA at any moment
without the risk of using an undefined transition. This comes at a high cost:
even for strongly connected partial DFAs, the shortest carefully synchronizing
words can have exponential length [38, Proposition 9], and the problem of
checking the existence of such a word is PSPACE-complete [38, Theorem 12], in
contrast with the case of complete DFAs. On the contrary, the notion of a
synchronizing partial DFA preserves most of the properties of a synchronizing
complete DFA, at least in the strongly connected case. Note that every
carefully synchronizing word is synchronizing, but the converse is not true.

While for complete DFAs the property of being strongly connected is not
essential for many synchronization properties [36], the situation changes
dramatically for partial DFAs. Partial DFAs, which are not strongly connected,
can have exponentially long shortest reset words, and the problem of checking
the existence of a reset word is PSPACE-complete [3]. Thus, strong
connectivity is indeed necessary to obtain good bounds and algorithms. As
explained above, for reactive systems and prefix codes this requirement comes
naturally.

1.6 Our contribution and organization of the paper We prove a number of
results for strongly connected partial DFAs connected with the Černý
conjecture and its generalizations. Where possible, we look up for methods
that allow relating the partial case with the complete case, instead of
directly reproving known results in this more general setting. In this way, we
do not have to go into the existing proofs, and future findings concerning the
complete case should be often immediately transferable to the partial case.

We start from basic properties and introduce more advanced techniques along
with their applications. First, we investigate the rank conjecture, which is a
generalization of the Černý conjecture from the case of synchronizing automata
to the case of all automata. We show that the rank conjecture for complete
DFAs implies it also for partial DFAs (Theorem 3.14). For this, we introduce
our first basic tool called _fixing automaton_ , which is a complete automaton
obtained from a partial one and sharing some properties. Our result shows a
general way for transferring upper bounds from the case of complete DFAs to
partial DFAs, e.g., we immediately get that the rank conjecture holds for
partial Eulerian automata (Corollary 3.16).

To connect the Černý conjecture for the cases of complete and partial DFAs, we
need more involved techniques, since the construction developed for the rank
conjecture does not preserve the property of being synchronizing. We introduce
a _collecting automaton_ , which extends the concept of the fixing automaton.
We use it to show that all upper bounds on the length of the shortest reset
words, up to a subquadratic additive component, are equivalent for partial and
complete DFAs (Theorem 3.26). We also use it to prove that the problems of
determining synchronizability and finding a reset word of a strongly connected
partial DFA can be effectively reduced to the same problem for a complete DFA
(Section 3.5). This also means that possible improvements of the complexity of
the best-known algorithms for these problems for complete DFAs should directly
apply to partial DFAs.

As discussed in 1.3 and 1.4, one of the main motivations for studying
synchronization of strongly connected partial DFAs is a direct correspondence
with synchronization of recognizable prefix codes. An important special case
is when the prefix code is finite. We investigate it by studying literal
automata of finite prefix codes and obtain stronger upper bounds than those
for the general case of strongly connected partial (or complete) DFAs. We show
that the length of the shortest reset words for literal automata of finite
prefix codes is at most $\mathcal{O}(n\log^{3}n)$, where $n$ is the number of
states of the automaton (Corollary 3.37). This upper bound is the same as the
best known for maximal prefix codes (which becomes now a special case), but it
is not transferred directly, as key statements do not hold in the same way for
non-maximal prefix codes. To prove it, we first show that literal automata of
finite prefix codes admit a word of linear length whose action sends all the
states to a non-empty subset of small size (Theorem 3.35). It establishes a
natural combinatorial property of finite prefix codes and constitutes the most
involved proof in this paper. Once we show the existence of such a word, we
use one more construction called the _induced automaton_ , which is a
generalization of linear algebraic techniques to the case of partial DFAs
(Section 3.7). This particular construction extends the existing techniques
originally developed for complete DFAs but simultaneously comes with a new
simpler and more general proof.

Finally, we show that the lower bounds for strongly connected partial DFAs are
asymptotically the same even if we ensure the existence of undefined
transitions (Section 4). In other words, undefined transitions do not help in
general, as we cannot significantly improve upper bounds for such automata
without doing that for the complete case.

##  2 Preliminaries

A _partial deterministic finite automaton_ $\mathrsfs{A}$ (which we call
_partial automaton_ throughout the paper) is a triple $(Q,\Sigma,\delta)$,
where $Q$ is a set of _states_ , $\Sigma$ is an _input alphabet_ , and
$\delta$ is partial function $Q\times\Sigma\to Q$ called the _transition
function_. Note that the automata we consider do not have any initial or final
states. We extend $\delta$ to a partial function $Q\times\Sigma^{*}\to Q$ as
usual: we set $\delta(q,wa)=\delta(\delta(q,w),a)$ for $w\in\Sigma^{*}$ and
$a\in\Sigma$. For a state $q\in Q$ and a word $w\in\Sigma^{*}$, if the action
$\delta(q,w)$ is undefined, then we write $\delta(q,w)=\bot$. Note that if
$\delta(q,w)=\bot$ for a word $w\in\Sigma^{*}$, then $\delta(q,wu)=\bot$ for
every word $u\in\Sigma^{*}$. An automaton is _complete_ if all its transitions
are defined, and it is _incomplete_ otherwise. An automaton is _strongly
connected_ if for every two states $p,q\in Q$ there is a word $w\in\Sigma^{*}$
such that $\delta(p,w)=q$.

By $\Sigma^{i}$ we denote the set of all words over $\Sigma$ of length exactly
$i$ and by $\Sigma^{\leq i}$ the set of all words over $\Sigma$ of length at
most $i$. For two sets of words $W_{1},W_{2}\in\Sigma^{*}$, by $W_{1}W_{2}$ we
denote their product $\\{w_{1}w_{2}\in\Sigma^{*}\mid w_{1}\in W_{1},w_{2}\in
W_{2}\\}$. The empty word is denoted by $\varepsilon$. Throughout the paper,
by $n$ we always denote the number of states $|Q|$.

Given $S\subseteq Q$, the _image_ of $S$ under the action of $w$ is
$\delta(S,w)=\\{\delta(q,w)\mid q\in S,\delta(q,w)\neq\bot\\}$. The _preimage_
of $S$ under the action of $w$ is $\delta^{-1}(S,w)=\\{q\in
Q\mid\delta(q,w)\in S\\}$. Since $\mathrsfs{A}$ is deterministic, for disjoint
subsets $S,T\subseteq Q$, their preimages under the action of every word
$w\in\Sigma^{*}$ are also disjoint.

The _rank_ of a word $w$ is the size of the image of $Q$ under the action of
this word, i.e., $|\delta(Q,w)|$. In contrast with complete automata, partial
automata may admit words of rank zero; these words are called _mortal_. Words
of non-zero rank are called _non-mortal_. A word of rank $1$ is called _reset_
, and if the automaton admits such a word then it is _synchronizing_. The
_reset threshold_ $\operatorname{rt}(\mathrsfs{A})$ is the length of the
shortest reset words of $\mathrsfs{A}$.

We say that a word $w$ _compresses_ a subset $S\subseteq Q$, if
$|\delta(S,w)|<|S|$ but $\delta(S,w)\neq\emptyset$. A subset that admits a
compressing word is called _compressible_. There are two ways to compress a
subset $S\subseteq Q$ with $|S|\geq 2$. One possibility is the _pair
compression_ , which is the same as in the case of a complete automaton, i.e.,
mapping at least two states $p,q\in S$ to the same state (but not to $\bot$).
The other possibility is to map at least one state from $S$ to $\bot$, but not
all states from $S$ to $\bot$. Sometimes, a subset can be compressed in both
ways simultaneously.

Figure 1: Left: a strongly connected partial 6-state binary automaton; right:
the literal automaton of the prefix code $\\{abaaa,abaab,abab,abba\\}$.

An example of a strongly connected partial automaton is shown in Fig. 1(left).
We have two undefined transitions: $\delta(q_{3},b)=\delta(q_{6},b)=\bot$. The
unique shortest reset word is $bab$: $\delta(Q,b)=\\{q_{1},q_{2},q_{5}\\}$,
$\delta(Q,ba)=\\{q_{2},q_{3},q_{6}\\}$, and $\delta(Q,bab)=\\{q_{2}\\}$.
However, in contrast with the case of a complete automaton, the preimage
$\delta^{-1}(\\{q_{2}\\},bab)=\\{q_{1},q_{4}\\}$ is not $Q$.

##  3 Upper Bounds

###  3.1 Inseparability Equivalence

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial automaton. We define the
inseparability relation $\equiv$ on $Q$. Two states are _separable_ if they
can be separated by mapping exactly one of them to $\bot$, leaving the other
one.

######  Definition 3.1.

The _inseparability equivalence_ $\equiv$ on $Q$ is defined as follows:

$p\equiv q\quad\text{ if and only if }\quad\forall_{u\in\Sigma^{*}}\
\left(\delta(p,u)\in Q\Leftrightarrow\delta(q,u)\in Q\right).$

The same relation is considered in [5, Section 1.4] if all states of the
partial automaton are final. Also, if we replace $\bot$ with a unique final
state, then $\equiv$ is the well-known Myhill-Nerode congruence on words in a
complete automaton. Under a different terminology, it also appears in the
context of $\varepsilon$-machines, where non-equivalent states are called
_topologically distinct_ [34].

For a subset $S\subseteq Q$, let $\kappa(S)$ be the number of equivalence
classes that have a non-empty intersection with $S$. In the automaton from
Fig. 1(left) we have three equivalence classes, where $q_{1}\equiv q_{4}$,
$q_{2}\equiv q_{5}$, and $q_{3}\equiv q_{6}$.

Our first auxiliary lemma states that a subset $S\subseteq Q$ that intersects
at least two equivalence classes can be compressed and the number of
intersected classes can be decreased with a short word. This is done by
mapping to $\bot$ all the states of $S$ from at least one equivalence class,
but not the whole set $S$. A linear upper bound can be inferred from a
standard analysis of the corresponding Myhill-Nerode congruence (e.g., [35]),
but we will need a more precise bound in terms of $\kappa(S)$.

######  Lemma 3.2.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial automaton, and let
$S\subseteq Q$ be a subset such that $\kappa(S)\geq 2$. Then there is a word
$w\in\Sigma^{*}$ of length at most $\kappa(Q)-\kappa(S)+1\leq n-|S|+1$ and
such that $1\leq\kappa(\delta(S,w))<\kappa(S)$.

######  Proof 3.3.

We define auxiliary relations on $Q$ that are restricted to words of certain
lengths. For $k\geq 0$, we define:

$p\equiv_{k}q\quad\text{ if and only if }\quad\forall_{u\in\Sigma^{\leq k}}\
\left(\delta(p,u)\in Q\Leftrightarrow\delta(q,u)\in Q\right).$

Clearly, $\equiv_{0}$ has all states in one equivalence class, and there is
some $m$ such that $\equiv_{m}$ is the same as $\equiv$ because the number of
different actions of words is finite. Also, for every $p,q\in Q$ and $k\geq
0$, if $q\not\equiv_{k}p$, then $q\not\equiv_{k+1}p$.

We show that if for some $k$, $\equiv_{k}$ is the same as $\equiv_{k+1}$, then
the chain of relations stabilizes at $\equiv$, i.e., all relations
$\equiv_{k},\equiv_{k+1},\equiv_{k+2},\ldots$ are the same as $\equiv$. Assume
for a contradiction that $\equiv_{k}$ is the same as $\equiv_{k+1}$, but
$\equiv_{k+2}$ is different from them. This means that there are two distinct
states $p,q\in Q$ such that $p\equiv_{k}q$, $p\equiv_{k+1}q$, and
$p\not\equiv_{k+2}q$. Hence, there exists a word $u$ of length $k+2$ such
that, without loss of generality, $\delta(p,u)=r\in Q$ and $\delta(q,u)=\bot$.
Write $u=av$, where $a\in\Sigma$ and $v\in\Sigma^{*}$. Then
$\delta(\\{p,q\\},a)=\\{p^{\prime},q^{\prime}\\}$ for some distinct states
$p^{\prime},q^{\prime}\in Q$. Since $|v|=k+1$, $\delta(p^{\prime},v)=r$ and
$\delta(q^{\prime},v)=\bot$, we have $p^{\prime}\not\equiv_{k+1}q^{\prime}$,
and from our assumption that $\equiv_{k}$ is the same as $\equiv_{k+1}$, we
also have $p^{\prime}\not\equiv_{k}q^{\prime}$. This means that there exists a
word $v^{\prime}$ of length at most $k$ such that
$\delta(p^{\prime},v^{\prime})=r^{\prime}\in Q$ and
$\delta(q^{\prime},v^{\prime})=\bot$, or vice versa. But then
$\delta(p,av^{\prime})=r^{\prime}$, $\delta(q,av^{\prime})=\bot$, and
$|av^{\prime}|\leq k+1$, which yields a contradiction with that
$p\equiv_{k+1}q$.

If for some $k$, $\equiv_{k+1}$ is different from $\equiv_{k}$, then the
number of equivalence classes in $\equiv_{k+1}$ is larger by at least one than
the number of equivalence classes in $\equiv_{k}$. Note that the number of
equivalence classes is limited by $\kappa(Q)$, so $\equiv_{\kappa(Q)-1}$ (and
every further relation) is the same as $\equiv$.

Observe that, for a $k\geq 0$, if $S$ is not contained in a single equivalence
class of $\equiv_{k}$, then there exists a word $w\in\Sigma^{\leq k}$ such
that, for some states $p,q\in S$, we have $\delta(p,w)\neq\bot$ and
$\delta(q,w)=\bot$, thus $w$ satisfies $1\leq\kappa(\delta(S,w))<\kappa(S)$.

We consider $\equiv_{\kappa(Q)-\kappa(S)+1}$. It has at least
$\kappa(Q)-\kappa(S)+2$ equivalence classes. Therefore, since there are at
most $\kappa(Q)-\kappa(S)$ equivalence classes not intersecting $S$, this
relation must have at least two classes that intersect $S$, so $S$ is not
contained in a single class. It follows that there is a word $w$ of length at
most $\kappa(Q)-\kappa(S)+1$ satisfying the lemma.

The second upper bound follows from the fact that there are at most $n-|S|$
equivalence classes in $Q\setminus S$, so $\kappa(Q)\leq n-|S|+\kappa(S)$.

By an iterative application of Lemma 3.2, we can easily compress any subset of
states to a subset of a single equivalence class.

######  Corollary 3.4.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial automaton, and let
$S\subseteq Q$ be a non-empty subset. There is a word $w$ of length at most
$(\kappa(S)-1)(\kappa(Q)-\kappa(S)/2)$ such that $\delta(S,w)$ is non-empty
and is contained in one inseparability class.

######  Proof 3.5.

In the worst case, we apply at most $\kappa(S)-1$ times Lemma 3.2 for subsets
intersecting $\kappa(S),\kappa(S)-1,\ldots,2$ equivalence classes.

###  3.2 Fixing Automaton

The other possibility of compressing a subset in a partial automaton is the
classical pair compression. This is the only way for compressing a subset with
all states in one equivalence class, which is always the case in a complete
automaton.

Our next tool to deal with this way of compression is the _fixing automaton_.
This is a complete automaton obtained from a partial one, defined as follows.

######  Definition 3.6 (Fixing automaton).

For a partial automaton $\mathrsfs{A}(Q,\Sigma,\delta)$, the _fixing
automaton_ is the complete automaton
$\mathrsfs{A}^{\mathrm{F}}=(Q,\Sigma,\delta^{\mathrm{F}})$ such that the
states are fixed instead of having an undefined transition: for every $q\in Q$
and $a\in\Sigma$, we have $\delta^{\mathrm{F}}(q,a)=q$ if $\delta(q,a)=\bot$,
and $\delta^{\mathrm{F}}(q,a)=\delta(q,a)$ otherwise.

We list some useful properties of the fixing automaton.

######  Lemma 3.7.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial automaton, let $S\subseteq
Q$, and let $w\in\Sigma^{*}$. We have
$\delta(S,w)\subseteq\delta^{\mathrm{F}}(S,w)$. Moreover, if for every state
$q\in S$ we have $\delta(q,w)\neq\bot$, then
$\delta(S,w)=\delta^{\mathrm{F}}(S,w)$.

######  Lemma 3.8.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial automaton and let
$S\subseteq Q$ be a non-empty subset. For every word $w\in\Sigma^{*}$, there
exists a word $w^{\prime}\in\Sigma^{*}$ of length $|w^{\prime}|\leq|w|$ such
that $\emptyset\neq\delta(S,w^{\prime})\subseteq\delta^{\mathrm{F}}(S,w)$. In
particular, if $w$ has rank $r$ in $\mathrsfs{A}^{\mathrm{F}}$, then
$w^{\prime}$ has rank $1\leq r^{\prime}\leq r$ in $\mathrsfs{A}$.

######  Proof 3.9.

For a letter $a\in\Sigma$, let $\delta^{-1}(\bot,a)=\\{q\in
Q\mid\delta(q,a)=\bot\\}$, which is the set of states that are mapped to
$\bot$ under the action of $a$ in $\mathrsfs{A}$.

We prove the statement by induction on the length $|w|$. Obviously, it holds
for $|w|=0$. Consider $w=ua$ for some $u\in\Sigma^{*}$ and $a\in\Sigma$, and
let $u^{\prime}$ be the word obtained from the inductive assumption for $u$.
Recall that all states from $\delta^{-1}(\bot,a)$ are fixed in
$\mathrsfs{A}^{\mathrm{F}}$ under the action of $a$. Let
$T=\delta(S,u^{\prime})$; thus $\emptyset\neq
T\subseteq\delta^{\mathrm{F}}(S,u)$ by the inductive assumption. We have two
cases.

  1. 1.

If $T\subseteq\delta^{-1}(\bot,a)$, then we let $w^{\prime}=u^{\prime}$.
Hence, we still have
$\delta(S,w^{\prime})=\delta(S,u^{\prime})=T\subseteq\delta^{\mathrm{F}}(S,ua)$,
because $T$ is fixed under the action of $a$ by $\delta^{\mathrm{F}}$.

  2. 2.

If $T\nsubseteq\delta^{-1}(\bot,a)$, then we let $w^{\prime}=u^{\prime}a$.
Since there is a state $q\in T\setminus\delta^{-1}(\bot,a)$, we know that
$\delta(T,a)$ is non-empty. We also have
$\delta(T,a)\subseteq\delta^{\mathrm{F}}(T,a)$, since the states in
$T\setminus\delta^{-1}(\bot,a)$ are mapped in the same way under the action of
$a$ by both $\delta$ and $\delta^{\mathrm{F}}$. We get that
$\delta(S,u^{\prime}a)=\delta(T,a)\subseteq\delta^{\mathrm{F}}(T,a)\subseteq\delta^{\mathrm{F}}(S,ua)$.

######  Corollary 3.10.

The minimal non-zero rank of a partial automaton $\mathrsfs{A}$ is at most the
minimal rank of $\mathrsfs{A}^{\mathrm{F}}$.

In the general case of a partial automaton, it can happen that we cannot
compress some subset $S$ even if there exists a word of non-zero rank smaller
than $|S|$. This is the reason why the shortest words of the minimal non-zero
rank can be exponentially long and why deciding if there is a word of a given
rank is PSPACE-complete [3].

However, in the case of a strongly connected partial automaton, as well as for
a complete automaton, every non-mortal word can be extended to a word of the
minimal non-zero rank. This is a fundamental difference that allows
constructing compressing words iteratively. Note that the fixing automaton of
a strongly connected partial one is also strongly connected.

######  Lemma 3.11.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial
automaton, and let $r$ be the minimal non-zero rank over all words. For every
non-empty subset $S\subseteq Q$, there exists a non-mortal word $w$ such that
$|\delta(S,w)|\leq r$.

######  Proof 3.12.

Let $u$ be a word of rank $r$. Then there exists a state $q\in Q$ such that
$\delta(q,u)$ is defined ($\neq\bot$). Let $p\in S$ be any state and let
$v_{p,q}$ be a word mapping $p$ to $q$ (from strong connectivity). Then
$\delta(S,v_{p,q}u)$ has a non-zero rank $\leq r$.

###  3.3 Rank Conjecture

The _rank conjecture_ (sometimes called _Černý-Pin conjecture_) is a well-
known generalization of the Černý conjecture to non-synchronizing automata
(e.g., [25]). The rank conjecture is a weaker version of the conjecture
originally stated by Pin that was not restricted to the minimal rank and
turned out to be false [18]. Some further results on the rank conjecture for
strongly connected complete automata are provided in [20].

######  Conjecture 3.13 (The rank conjecture).

For an $n$-state complete automaton where $r$ is the minimal rank over all
words, there exists a word of rank $r$ and of length at most $(n-r)^{2}$.

For partial automata, the rank conjecture is analogous with the exception that
$r$ is the minimal non-zero rank.

######  Theorem 3.14.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial
automaton. If the rank conjecture holds for the fixing automaton
$\mathrsfs{A}^{\mathrm{F}}$, then it also holds for $\mathrsfs{A}$.

######  Proof 3.15.

Let $r$ be the minimal rank in $\mathrsfs{A}^{\mathrm{F}}$ over all words.
From the conjecture and by Lemma 3.8, there exists a word $w^{\prime}$ of
length at most $(n-r)^{2}$ and such that
$\emptyset\neq\delta(Q,w^{\prime})\subseteq\delta^{\mathrm{F}}(Q,w)$.

Let $r^{\prime}\leq r$ be the minimal rank of $\mathrsfs{A}$. For every
$s=r,r-1,\ldots,r^{\prime}+1$, we inductively construct a word of non-zero
rank less than $s$, of length at most $(n-(s-1))^{2}$, and such that
$w^{\prime}$ is its prefix. Let $w^{\prime}v$ be a word of rank at most $s$
and of length at most $(n-s)^{2}$, and let $S=\delta(Q,w^{\prime}v)$. Suppose
that $\kappa(S)=1$. Since $s$ is not the minimal rank of $\mathrsfs{A}$, by
Lemma 3.11, $S$ must be compressible. Since its states are inseparable, there
must be two distinct states $p,q\in S$ and a word $u$ such that
$\delta(q,u)=\delta(p,u)\neq\bot$. But (from Lemma 3.7)
$\\{p,q\\}\subseteq\delta(Q,w^{\prime}v)\subseteq\delta^{\mathrm{F}}(Q,w^{\prime}v)\subseteq\delta^{\mathrm{F}}(Q,wv)$,
thus $\delta^{\mathrm{F}}(Q,wv)$ is compressible in
$\mathrsfs{A}^{\mathrm{F}}$, which contradicts that $w$ has the minimal rank
in $\mathrsfs{A}^{\mathrm{F}}$. Hence $\kappa(S)\geq 2$, and by Lemma 3.2,
$\delta(Q,w^{\prime}v)$ can be compressed with a word $u$ of length at most
$n-s+1$. We have $|w^{\prime}vu|\leq(n-s)^{2}+n-s+1\leq(n-(s-1))^{2}$, which
proves the induction step.

The theorem implies that, in the strongly connected case, the rank conjecture
is true for complete automata if and only if it is true for partial automata.
For instance, we immediately get the result for the class of Eulerian
automata. A partial automaton is _Eulerian_ if it is strongly connected and
the numbers of outgoing and incoming transitions are the same at every state,
i.e., for every $q\in Q$, we have $|\\{a\in\Sigma\mid\delta(q,a)\in
Q\\}|=|\\{(p,a)\in Q\times\Sigma\mid\delta(p,a)=q\\}|$. The following
corollary follows from the facts that the rank conjecture holds for complete
Eulerian automata [20] and that the fixing automaton of a partial Eulerian
automaton is also Eulerian.

######  Corollary 3.16.

The rank conjecture is true for partial Eulerian automata.

###  3.4 Collecting Automaton

The fixing automaton allows relating the behavior of words in a partial and a
complete automaton, but its main disadvantage is that it is not necessarily
synchronizing. Therefore, we will need one more tool, called _collecting
automaton_. It is an extension of the fixing automaton by an additional letter
that allows a quick synchronization into one inseparability class, while it
does not affect the length of a shortest synchronizing word for any particular
inseparability class.

By
$\mathrsfs{A}/_{\equiv}=(Q_{\mathrsfs{A}/_{\equiv}},\Sigma,\delta_{\mathrsfs{A}/_{\equiv}})$,
we denote the quotient automaton by the inseparability relation.
$\mathrsfs{A}/_{\equiv}$ is also a partial automaton, and if $\mathrsfs{A}$ is
strongly connected, then so is $\mathrsfs{A}/_{\equiv}$. By $[p]\in
Q_{\mathrsfs{A}/_{\equiv}}$, we denote the class of a state $p\in Q$ of the
original automaton $\mathrsfs{A}$.

A _collecting tree_ of $\mathrsfs{A}$ is a tree $T$ with the set of vertices
$Q_{\mathrsfs{A}/_{\equiv}}$ and directed edges labeled by letters from
$\Sigma$ in the following way: (a) Edges are labeled by letters from $\Sigma$
and correspond to transitions in $\mathrsfs{A}/_{\equiv}$: each edge
$([p],[p^{\prime}],a)$ is such that
$\delta_{\mathrsfs{A}/_{\equiv}}([p],a)=[p^{\prime}]$. (b) There is a root
$[r]$ such that the tree is directed toward it. See Fig. 2 in Appendix for an
example. Equivalently, it can be seen as a specific partial automaton being a
subautomaton of $\mathrsfs{A}/_{\equiv}$ whose underlying digraph is a tree
directed toward one state. An automaton can have many collecting trees, even
for the same $[r]$, and every strongly connected automaton has a collecting
tree for every class $[r]$.

Figure 2: Left: a collecting tree with root $[q3]=\\{q_{3},q_{6}\\}$; right:
the corresponding collecting automaton of the example from Fig. 1(left).

######  Definition 3.17 (Collecting automaton).

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial automaton
and let $T$ be one of its collecting trees with a root $[r]$. The _collecting
automaton_
$\mathrsfs{A}^{\mathrm{C}(T)}=(Q,\Sigma\cup\\{\gamma\\},\delta^{\mathrm{C}(T)})$
is defined as follows:

  * •

The transition function $\delta^{\mathrm{C}(T)}$ on $\Sigma$ is defined as in
the fixing automaton $\mathrsfs{A}^{\mathrm{F}}$.

  * •

$\gamma\notin\Sigma$ is a fresh letter. Its action is defined according to the
edges in $T$: Let $q_{1}\in Q\setminus[r]$ be a state. Since $T$ is a tree
directed toward $[r]$, there is exactly one edge outgoing from $[q_{1}]$, say
$([q_{1}],[q_{2}],a)\in T$ for some $[q_{2}]\in Q_{\mathrsfs{A}/_{\equiv}}$
and $a\in\Sigma$. We set
$\delta^{\mathrm{C}(T)}(q_{1},\gamma)=\delta(q_{1},a)$. Finally, the
transition of $\gamma$ on each state in $[r]$ is the identity.

A collecting automaton is always strongly connected, as it contains all
transitions of the fixing automaton. We prove several properties connecting
partial automata and their collecting complete automata. They are preliminary
steps toward relating the Černý conjecture for strongly connected partial and
complete automata.

######  Lemma 3.18.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial
automaton, and let $T$ be one of its collecting trees with a root $[r]$. If
there is a word over $\Sigma\cup\\{\gamma\\}$ synchronizing $[r]$ in
$\mathrsfs{A}^{\mathrm{C}(T)}=(Q,\Sigma\cup\\{\gamma\\},\delta^{\mathrm{C}(T)})$,
then there is such a word over $\Sigma$ that is not longer.

######  Proof 3.19.

Let $w^{\prime}\in(\Sigma\cup\\{\gamma\\})^{*}$ be a word synchronizing $[r]$
in $\mathrsfs{A}^{\mathrm{C}(T)}$. We construct $w\in\Sigma^{*}$ from
$w^{\prime}$ such that $w$ also synchronizes $[r]$ and $|w|\leq|w^{\prime}|$.
This is done by replacing every occurrence of $\gamma$ in $w^{\prime}$ with a
suitable substituting letter from $\Sigma$ or removing it.

Consider an occurrence of $\gamma$ in $w^{\prime}$, so let $w^{\prime}=u\gamma
v$, for some $u,v\in(\Sigma\cup\\{\gamma\\})^{*}$. Let $[p]$ be the class such
that $\delta^{\mathrm{C}(T)}([r],u)\subseteq[p]$. If $[p]\neq[r]$, then let
$a\in\Sigma$ be the letter labeling the outgoing edge $([p],[p^{\prime}],a)$
in the collecting tree. The action of $a$ on $[p]$ is thus the same as the
action of $\gamma$. Hence, $\delta^{\mathrm{C}(T)}([r],u\gamma
v)=\delta^{\mathrm{C}(T)}([r],uav)$. If $[p]=[r]$, then $\gamma$ acts as
identity on $[p]$, thus $\delta^{\mathrm{C}(T)}([r],u\gamma
v)=\delta^{\mathrm{C}(T)}([r],uv)$.

We can consider the $\gamma$ occurrences in any order and the obtained word
$w$ have the property that
$\delta^{\mathrm{C}(T)}([r],w^{\prime})=\delta^{\mathrm{C}(T)}([r],w)$, thus
synchronizes $[r]$ as $w^{\prime}$ does.

######  Lemma 3.20.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial automaton
and let $T$ be one of its collecting trees. Then $\mathrsfs{A}$ is
synchronizing if and only if the collecting automaton
$\mathrsfs{A}^{\mathrm{C}(T)}=(Q,\Sigma\cup\\{\gamma\\},\delta^{\mathrm{C}(T)})$
is synchronizing.

######  Proof 3.21.

Let $[r]$ be the root class of $T$. Let $w\in\Sigma^{*}$ be a reset word for
$\mathrsfs{A}$. Then there is some class $[p]$ such that $w$ synchronizes it.
By Lemma 3.7, $\delta([p],w)=\delta^{\mathrm{F}}([p],w)$ is a singleton. Since
$\mathrsfs{A}$ is strongly connected, there is a word $u_{r\to p}$ whose
action maps all states from $[r]$ into $[p]$. Then $\gamma^{n-1}u_{r\to p}w$
is a synchronizing word for $\mathrsfs{A}^{\mathrm{C}(T)}$.

Conversely, if $\mathrsfs{A}^{\mathrm{C}(T)}$ is synchronizing, in particular
there exists a word synchronizing $[r]$. By Lemma 3.18, there is also a word
$w$ synchronizing $[r]$ in $\mathrsfs{A}^{\mathrm{C}(T)}$. By Corollary 3.4,
we can find a word $v$ whose action maps $Q$ into a single equivalence class
$[p]$. By strong connectivity, we can find a word $u_{p\to r}$ that maps all
states from $[p]$ into $[r]$. Thus, $vu_{p\to r}w$ is a reset word for
$\mathrsfs{A}$.

This also means that the choice of $T$ does not matter:
$\mathrsfs{A}=(Q,\Sigma,\delta)$ is synchronizing if and only if all
$\mathrsfs{A}^{\mathrm{C}(T)}$ are synchronizing.

###  3.5 Algorithmic Issues

Checking if a strongly connected partial automaton is synchronizing and
finding a minimum-rank word can be done similarly as for a complete automaton,
by a suitable generalization of the well-known Eppstein algorithm [13,
Algorithm 1]. The same algorithm for checking synchronizability, under
different terminology, was described in the context of $\varepsilon$-machines
[34].

######  Proposition 3.22.

Checking if a given strongly connected partial automaton with $n$ states over
an alphabet $\Sigma$ is synchronizing can be done in
$\mathcal{O}(|\Sigma|n^{2})$ time and $\mathcal{O}(n^{2}+|\Sigma|n)$ space.
Finding a word of the minimum rank can be done in $\mathcal{O}(|\Sigma|n^{3})$
time and $\mathcal{O}(n^{2}+|\Sigma|n)$ space.

######  Proof 3.23.

We modify the well-known Eppstein algorithm [13, Algorithm 1] by generalizing
it to partial and not necessarily synchronizing automata. We mark all pairs of
states $\\{p,q\\}$ such that $|\delta(\\{p,q\\},a)|=1$ for some $a\in\Sigma$
(note that this includes two possibilities of compression) and propagate the
compressibility backwards. If all pairs are compressible, then the automaton
is synchronizing. Then starting from $Q$, we repetitively apply a shortest
word compressing a pair of states in the current subset. The algorithm stops
when the subset is no longer compressible, and by Lemma 3.11, its size is
equal to the minimal rank.

Furthermore, the problem of checking the synchronizability of a strongly
connected partial automaton can be reduced in smaller time to the case of a
complete automaton.

######  Theorem 3.24.

Given a strongly connected partial automaton, we can construct in
$\mathcal{O}(|\Sigma|n\log n)$ time a complete automaton that is synchronizing
if and only if the given partial automaton is synchronizing.

######  Proof 3.25.

We can compute all inseparability classes in $\mathcal{O}(|\Sigma|n\log n)$
time. This is done by the Hopcroft minimization algorithm [15], if we
interpret the partial DFA as a language-accepting DFA with an arbitrary
initial state and the sink state $\bot$ that is its only final state.

Having computed the classes, we can construct a collecting automaton for an
arbitrary collecting tree. Note that it can be done in
$\mathcal{O}(|\Sigma|n)$ time by a breadth-first search from a class $[r]$.
The desired property follows from Lemma 3.20.

###  3.6 Černý Conjecture

The famous Černý conjecture is the rank conjecture for $r=1$. Let
$\mathfrak{C}(n)$ be the maximum length of the shortest reset words of all
$n$-state synchronizing complete automata. It is well known that
$\mathfrak{C}(n)\geq(n-1)^{2}$ [8]. The Černý conjecture states that
$\mathfrak{C}(n)=(n-1)^{2}$, but the best proved upper bound is cubic [32,
33].

Let $\mathfrak{C}_{\mathrm{P}}(n)$ be the maximal length of the shortest reset
words of all $n$-state synchronizing strongly connected partial automata. We
show that if the Černý conjecture is true (or another upper bound holds), then
a slightly weaker upper bound holds for synchronizing strongly connected
partial automata.

To prove the following theorem, we combine several techniques, in particular,
the inseparability equivalence, the collecting automaton, and an algebraic
upper bound on the reset threshold of a complete automaton with a word of
small rank [4].

######  Theorem 3.26.

$\mathfrak{C}_{\mathrm{P}}(n)\leq\mathfrak{C}(n)+\mathcal{O}(n^{4/3}).$

######  Proof 3.27.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a synchronizing partial automaton with
$n$ states. Let $T$ be a collecting tree of $\mathrsfs{A}$ with a root class
$[r]$ containing the smallest number of states. We consider the collecting
automaton
$\mathrsfs{A}^{\mathrm{C}(T)}=(Q,\Sigma\cup\\{\gamma\\},\delta^{\mathrm{C}(T)})$.
By Lemma 3.20, $\mathrsfs{A}^{\mathrm{C}(T)}$ is synchronizing. We have two
cases, depending on the number $\kappa(Q)$ of inseparability classes of
$\mathrsfs{A}$.

First, suppose that $\kappa(Q)\leq n^{2/3}$. Then, by Corollary 3.4 (for
$S=Q$), there is a word $v$ of length at most
$(\kappa(Q)-1)\kappa(Q)/2<n^{4/3}$ such that $\delta(Q,v)$ is non-empty and is
contained in one equivalence class, say $[p]$. Since $\mathrsfs{A}$ is
strongly connected, there is a word $u_{p\to r}$ of length at most $n-1$ whose
action maps $[p]$ into $[r]$. Let $w^{\prime}$ be a reset word for
$\mathrsfs{A}^{\mathrm{C}(T)}$ of length at most $\mathfrak{C}(n)$. In
particular, $w^{\prime}$ synchronizes $[r]$, so by Lemma 3.18, we get a word
$w$ of length at most $\mathfrak{C}(n)$ that synchronizes $[r]$ in
$\mathrsfs{A}$. Then, $vu_{p\to r}w$ is a reset word for $\mathrsfs{A}$ of
length at most $n^{4/3}+n-1+\mathfrak{C}(n)$.

In the second case, we have $\kappa(Q)>n^{2/3}$. Then the size of $[r]$, which
has been chosen to have the smallest size, has at most $n^{1/3}$ states. Note
that $\gamma^{n-1}$ is a word of rank at most $n^{1/3}$. Then we can apply
Corollary 3.31 (cf. [4, Theorem 2]) for $\mathrsfs{A}^{\mathrm{C}(T)}$ with
this word, obtaining that the reset threshold of
$\mathrsfs{A}^{\mathrm{C}(T)}$ is upper bounded by
$(n-1)+2(n-1)\mathfrak{C}(n^{1/3})$. Using the well-known general cubic upper
bound $n^{3}/6$ on the reset threshold of a complete automaton (e.g., [25]),
we get that there is a reset word $w^{\prime}$ for
$\mathrsfs{A}^{\mathrm{C}(T)}$ of length at most $(n-1)+2(n-1)n/6$. Now, we
return to $\mathrsfs{A}$. By Corollary 3.4 (for $S=Q$), we get a word $v$ of
length at most $(n-1)n/2$ such that $\delta(Q,u)$ is non-empty and is
contained in one equivalence class $[p]$. As in the first case, there is a
word $u_{p\to r}$ of length at most $n-1$ whose action maps $[p]$ into $[r]$.
By Lemma 3.18, from $w^{\prime}$ we obtain a word $w$ that synchronizes $[r]$
and is no longer than $(n-1)+2(n-1)n/6$. Finally, $vu_{p\to r}w$ is a reset
word for $\mathrsfs{A}$ of length at most
$(n-1)n/2+(n-1)+(n-1)+2(n-1)n/6\leq(n-1)^{2}$ for $n\geq 18$.

From both cases, we conclude that
$\operatorname{rt}(\mathrsfs{A})\leq\mathfrak{C}(n)+\mathcal{O}(n^{4/3})$.

From Theorem 3.26, it follows that all upper bounds on the reset threshold of
a complete automaton transfer to upper bounds for partial automata, up to a
subquadratic component. Thus $\mathfrak{C}_{\mathrm{P}}(n)\leq
0.1654n^{3}+\mathcal{O}(n^{2})$ [32]. It can be also seen from the proof that
if we have a better general upper bound on $\mathfrak{C}(n)$, we get a smaller
additional term, e.g., if $\mathfrak{C}(n)\in\mathcal{O}(n^{2})$, then
$\mathfrak{C}_{\mathrm{P}}(n)=\mathfrak{C}(n)+\mathcal{O}(n)$, so the
additional term is at most linear. The additional component is likely not
needed, but it is difficult to completely get rid of it in general, as for
that we could not lengthen by any means the reset word assumed for a complete
automaton. However, it is easy to omit it when reproving particular bounds for
complete automata, both combinatorial [25] and based on avoiding words [32,
33]. We conjecture that $\mathfrak{C}_{\mathrm{P}}(n)=\mathfrak{C}(n)$ for all
$n$.

###  3.7 Induced Automaton

We develop an algebraic technique applied to partial automata. It will allow
us deriving upper bounds on reset thresholds, in particular, in the cases when
there exists a short word of a small rank, which is the case of the literal
automaton of a prefix code. We base on the results from [4] for complete
automata and generalize them to be applied to partial automata. The existing
linear algebraic proofs for complete automata do not work for partial ones,
because the matrices of transitions may not have a constant sum of the entries
in each row.

We need to introduce a few definitions from linear algebra for automata (see,
e.g., [4, 19, 24, 33]). Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a partial DFA.
Without loss of generality we assume that $Q=\\{1,\ldots,n\\}$. By
$\mathbb{R}^{n}$, we denote the real $n$-dimensional linear space of row
vectors. For a vector $v\in\mathbb{R}^{n}$ and an $i\in Q$, we denote the
vector’s value at the $i$-th position by $v(i)$. Similarly, for a matrix $M$,
we denote its value in an $i$-th row and a $j$-th column by $M(i,j)$. A vector
$g$ is _non-negative_ if $g(i)\geq 0$ for all $i$, and it is _non-zero_ if
$g(i)\neq 0$ for some $i$. For a word $w\in\Sigma^{*}$, by $\mathrm{M}(w)$ we
denote the $n\times n$ matrix of the transformation of $w$ in $\delta$:
$\mathrm{M}(w)(p,q)=1$ if $\delta(p,w)=q$, and $\mathrm{M}(w)(p,q)=0$
otherwise. Note that if $\delta(p,w)=\bot$, then we have
$\mathrm{M}(w)(p,q)=0$ for all $q\in Q$. The usual scalar product of two
vectors $u,v$ is denoted by $u\odot v$. The linear subspace _spanned_ by a set
of vectors $V$ is denoted by $\operatorname{span}(V)$.

Given a transition function $\delta$ (which defines matrices $\mathrm{M}(w)$),
call a set of words $W\subseteq\Sigma^{*}$ _complete for a subspace_
$V\subseteq\mathbb{R}^{n}$ _with respect to a vector_ $g\in V$, if
$V\subseteq\operatorname{span}(\\{g\mathrm{M}(w)\mid w\in W\\})$. A set of
words $W\subseteq\Sigma^{*}$ is _complete for a subspace_
$V\subseteq\mathbb{R}^{n}$ if for every non-negative non-zero vector $g\in V$,
$W$ is complete for $V$ with respect to $g$. Let $\chi(p)$ denote the
characteristic (unitary) vector of $\\{p\\}$. For a subset $S\subseteq Q$, we
define $\mathbb{V}(S)=\operatorname{span}(\\{\chi(p)\mid p\in
S\\})\subseteq\mathbb{R}^{n}$.

For example, consider the automaton from Fig. 1(left). Let
$V=\mathbb{V}(\\{q_{1},q_{2},q_{5}\\})$ and let $W=\\{ab,aab\\}a^{\leq 5}$.
Let $g\in V$ be a non-negative non-zero vector, and let $i$ be such that
$g(i)\neq 0$. If $i=1$ then let $u=ab$, and otherwise let $u=aab$; then
$g\mathrm{M}(u)$ has exactly one non-zero entry. Then, for each
$j\in\\{1,2,5\\}$, the vector $g\mathrm{M}(ua^{j^{\prime}})$ for some
$j^{\prime}$ has the unique non-zero entry at $q_{j}$. These vectors generate
$V$, thus $W$ is complete for $V$ with respect to $g$.

The induced automaton of a partial one is another partial automaton acting on
a subset of states $R\subseteq Q$. It is built from two sets of words. Let
$W_{1}$ be a set of words such that $R=\bigcup_{w\in W_{1}}\delta(Q,w)$. For
each state in $R$, there is some state mapped to it by a word from $W_{1}$.
The second set $W_{2}$ is any non-empty set of words that enriches its
transitions. The induced automaton is $\mathrsfs{A}$ restricted to $R$ with
alphabet $W_{2}W_{1}$. Note that its transition function is well defined,
which is ensured by the fact that every word of the form $w_{2}w_{1}\in
W_{2}W_{1}$ has the action mapping every state $q\in Q$ into $R$ or to $\bot$.

######  Definition 3.28 (Induced automaton).

Let $W_{1},W_{2}\subseteq\Sigma^{*}$ be non-empty and $R=\\{\delta(q,w)\mid
q\in Q,\ w\in W_{1},\delta(q,w)\neq\bot\\}$. If $R$ is non-empty, we define
the _induced automaton_
$\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}=(R,W_{2}W_{1},\delta_{\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}})$,
where the transition function is defined in compliance with the actions of
words in $\mathrsfs{A}$, i.e.,
$\delta_{\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}}(q,w)=\delta(q,w)$ for all
$q\in R$ and $w\in W_{2}W_{1}$.

We can analyze an induced automaton as a separate one, and synchronize the
whole automaton using it, which is particularly profitable when $R$ is small.
Following our previous example, for Fig. 1(left) with $W_{1}=\\{b\\}$ and
$W_{2}=\\{ab,aab\\}a^{\leq 5}$ we obtain the induced automaton on
$R=\\{q_{1},q_{2},q_{5}\\}$. Furthermore, it is synchronizing already by a
letter from $W_{2}W_{1}$ (e.g., $abb$), and each its reset word corresponds to
a reset word of the original $\mathrsfs{A}$.

The following lemma states that the completeness of a set of words together
with the synchronizability and strong connectivity of the whole automaton
transfer to the induced automaton. It generalizes [4, Theorem 2] to partial
automata, and the proof uses a recursion instead of an augmenting argument.

######  Lemma 3.29.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected synchronizing
partial automaton and let $W_{1}$ and $W_{2}$ be two non-empty sets of words
over $\Sigma$. Let
$\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}=(R,W_{2}W_{1},\delta_{\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}})$
be the induced automaton. If $W_{2}$ is complete for
$\mathbb{V}(Q)=\mathbb{R}^{n}$, then $W_{2}W_{1}$ is complete for
$\mathbb{V}(R)$, and $\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}$ is synchronizing
and strongly connected.

######  Proof 3.30.

First, let us prove the completeness of $W_{2}W_{1}$ for $\mathbb{V}(R)$ with
respect to an arbitrary non-negative non-zero vector $\alpha\in\mathbb{V}(R)$.
By the definition of $R$, for each state $r\in R$, there is a state $q_{1}$
and a word $u_{1}\in W_{1}$ such that $\delta(q_{1},u_{1})=r$. Since
$\mathrsfs{A}=(Q,\Sigma,\delta)$ is synchronizing and strongly connected,
there is a synchronizing word $u_{2}$ such that $\delta(Q,u_{2})=\\{q_{1}\\}$.
Since the image is non-empty, there is a state $q_{2}\in Q$ such that
$\delta(q_{2},u_{2})=q_{1}$. Let $q_{3}\in R$ be a state such that
$\chi(q_{3})\odot\alpha>0$ (it exists since $\alpha\in\mathbb{V}(R)$ is non-
zero). Again by the strong connectivity of $\mathrsfs{A}$, there is a word
$u_{3}$ whose action maps $q_{3}$ to $q_{2}$. Hence, $u_{3}u_{2}u_{1}$ is a
synchronizing word with the action mapping $q_{3}$ to $r$. Thus
$\alpha\mathrm{M}(u_{3}u_{2}u_{1})\in\operatorname{span}(\\{\chi(r)\\})$, and
since $\alpha$ and $\mathrm{M}(u_{3}u_{2}u_{1})$ are also non-negative,
$(\alpha\mathrm{M}(u_{3}u_{2}u_{1}))(r)\neq 0$. Since this holds for every
$r\in R$, that is, for every $r$ we can find a word $u_{3}u_{2}u_{1}$ that
yields a vector with non-zero $r$-th entry and all the other entries
containing zero. Moreover, these words are from $\Sigma^{*}W_{1}$, thus we get
$\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid
w\in\Sigma^{*}W_{1}\\})=\mathbb{V}(R)$. As $W_{2}$ is complete for
$\mathbb{V}(Q)$, for each $w\in\Sigma^{*}$, we have
$\alpha\cdot\mathrm{M}(w)\in\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w_{2})\mid
w_{2}\in W_{2}\\})$. This implies that
$\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid w\in
W_{2}W_{1}\\})=\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid
w\in\Sigma^{*}W_{1}\\})=\mathbb{V}(R)$.

It remains to prove that $\mathrsfs{B}=\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}$
is synchronizing. If $|R|=1$, we are done, so consider $|R|\geq 2$. Suppose
that $R$ is not compressible in $\mathrsfs{B}$. Then, for each word $w\in
W_{2}W_{1}$, we have $\delta(R,w)=R$ or $\delta(R,w)=\emptyset$. This
contradicts with $W_{2}W_{1}$ being complete for $\mathbb{V}(R)$ with respect
to $\chi(R)$ since $\operatorname{span}(\\{\chi(R)\cdot\mathrm{M}(w)\mid w\in
W_{2}W_{1}\\})\subseteq\operatorname{span}(\\{\chi(R)\\})\subsetneq\mathbb{V}(R)$.
Hence $R$ is compressible in $\mathrsfs{B}$ and the statement follows by
induction. Note that the conditions of the lemma are met for the induced
automaton
$\mathrsfs{A}^{\mathrm{I}(W_{1}\\{w\\},W_{2})}=(\delta(R,w),W_{2}W_{1}\\{w\\},\delta_{\mathrsfs{A}^{\mathrm{I}(W_{1}\\{w\\},W_{2})}})$,
where $w\in W_{2}W_{1}$ is a word that compresses $R$.

The following corollary directly follows from Lemma 3.29, since $\Sigma^{\leq
n-1}$ is always complete for $\mathbb{V}(Q)$ in the case of a strongly
connected synchronizing partial automaton.

######  Corollary 3.31.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected synchronizing
partial automaton with $n$ states, and let $w\in\Sigma^{*}$ be a word such
that $R=\delta(Q,w)\neq\emptyset$. Let $W_{1}=\\{w\\}$, $W_{2}=\Sigma^{\leq
n-1}$, and $\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}=(R,\Sigma^{\leq
n-1}\\{w\\},\delta_{\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}})$ be the induced
automaton. Then
$\operatorname{rt}(\mathrsfs{A})\leq|w|+(|w|+n-1)\cdot\operatorname{rt}(\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})})$.

######  Proof 3.32.

Let $\alpha$ be a non-negative non-zero vector, and let $q\in Q$ be such that
$\chi(q)\odot\alpha>0$. Since the automaton is strongly connected and
synchronizing, for every $p\in Q$, there is a word $u_{p}$ such that
$\delta(Q,u_{p})=\\{p\\}$ and furthermore $\delta(q,u_{p})=p$. It follows that
$\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid
w\in\Sigma^{*}\\})=\mathbb{V}(Q)$. By the usual ascending chain argument
(e.g., [19, 24, 33]), $\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid
w\in\Sigma^{\leq n-1}\\})=\operatorname{span}(\\{\alpha\cdot\mathrm{M}(w)\mid
w\in\Sigma^{*}\\})=\mathbb{V}(Q)$. Thus, we can apply Lemma 3.29 for the
induced automaton.

It is useful for deriving upper bounds for automata with a word of small rank.
Having such a word $w$, we can further synchronize $R$ through the induced
automaton instead of trying to do this directly. Although every letter of
$\mathrsfs{A}^{\mathrm{I}(W_{1},W_{2})}$ corresponds to a word of length
$|w|+n-1$ in the original $\mathrsfs{A}$, if $R$ is small enough, this yields
a better upper bound. We show its application in the next subsection.

###  3.8 The Literal Automaton of a Finite Prefix Code

We use the obtained results about induced automata to get better bounds for
partial literal automata of finite prefix codes. To do so, we first need to
prove that such automata admit short enough words of small rank. It is known
that every complete literal automaton over an alphabet $\Sigma$ has a word of
rank and length at most $\lceil\log_{|\Sigma|}n\rceil$ ([4, Lemma 16], cf. [6,
Lemma 14]). However, this is no longer true for non-mortal words in partial
literal automata [29] and no similar statement was known for any wider class
than complete literal automata. We prove that there exist $\mathcal{O}(\log
n)$-rank non-mortal words of length $\mathcal{O}(n)$ in such automata,
excluding the case of a code with only one word. Then we use this result to
provide an $\mathcal{O}(n\log^{3}n)$ upper bound on the reset threshold of
$n$-state synchronizing partial literal automata, matching the known upper
bound for complete literal automata [4].

We start with a special case of one-word codes. A non-empty word $w$ is called
_primitive_ if it is not a power of another word, i.e., $w\neq u^{k}$ for
every word $u$ and $k\geq 2$. The upper bound on
$\operatorname{rt}(\mathrsfs{A}_{X})$ follows from a result of Weinbaum ([14,
39]).

######  Proposition 3.33.

Let $X=\\{x\\}$ be a one-word prefix code, and suppose that $x=y^{k}$, where
$y$ is a non-empty primitive word and $k\geq 1$. Then $\mathrsfs{A}_{X}$ has
rank $k$. If $\mathrsfs{A}_{X}$ is synchronizing, then
$\operatorname{rt}(\mathrsfs{A}_{X})\leq\frac{|x|}{2}$, and this bound is
tight.

######  Proof 3.34.

Observe that the literal automaton of a one-word code forms as a single cycle
labeled by the letters of this word. No two states can be mapped to a single
state by the action of any letter, which excludes pair compression.

Observe that $\mathrsfs{A}_{X}/_{\equiv}$ is the literal automaton
$\mathrsfs{A}_{Y}$ of $Y=\\{y\\}$. In $\mathrsfs{A}_{X}$, there are $n/k$
inseparability classes, each of size $k$. Hence, the rank of
$\mathrsfs{A}_{X}$ equals $k$ times the rank of $\mathrsfs{A}_{Y}$. Since $y$
is primitive, its action is defined only for the root state (and maps the root
to itself). Thus $\mathrsfs{A}_{Y}$ is synchronizing, so the rank of
$\mathrsfs{A}_{X}$ equals $k$.

Now, we will bound the length of the shortest reset words. A word $t$ is
called a _conjugate_ of $t^{\prime}$ if $t=uv$ and $t^{\prime}=vu$ for some
words $u,v$. By a result of Weinbaum, stated in terms of automata, every
primitive word $x$ has a conjugate $x^{\prime}=uv$ such that both $u$ and $v$
have the action defined exactly for one state of $\mathrsfs{A}_{X}$ [14].
Thus, both $u$ and $v$ are reset for $\mathrsfs{A}_{X}$. The shorter of them
has length at most $\frac{|x|}{2}$.

To see that the bound can be met, consider the code $Z=\\{a^{k}ba^{k+1}b\\}$.
The shortest reset word for $\mathrsfs{A}_{Z}$ is $a^{k+1}$ of length
$\lfloor\frac{2k+3}{2}\rfloor=k+1$.

In the remaining cases, there always exists a word of linear length and
logarithmic rank.

######  Theorem 3.35.

Let $X$ be a prefix code with at least two words. Let
$\mathrsfs{A}_{X}=(Q,\Sigma,\delta)$ be its partial literal automaton with $n$
states and height $h$. Then there exists a word of length at most $2h$ and of
rank at most $\lceil\log_{2}hn\rceil+\lceil\log_{2}h\rceil$ for
$\mathrsfs{A}_{X}$. Moreover, such a word can be found in polynomial time in
$n=|Q|$.

######  Proof 3.36.

The general idea is as follows. We construct a word from the theorem in two
phases. First, we define an auxiliary _filtering_ algorithm computing some
function $\alpha\colon\Sigma^{*}\to\Sigma^{*}$. We consider the results of the
algorithm for a lot of short (logarithmic) input words $w$ and show that at
least one of them satisfies that $\alpha(w)$ is non-mortal, has length at most
$h$, and every state from $Q$ is either sent to $\bot$ or goes through the
root by its action. Then, we use specific properties of the image
$\delta(Q,\alpha(w))$ to divide it into two disjoint sets: one that has up to
$h$ states, but on a single specific path, and the other one with a small
(logarithmic) number of states. In the second phase, we construct a word $v$
of length also bounded by $h$, such that its action map all the states from
the mentioned specific path to a subset of at most logarithmic size. The
concatenation of both words $\alpha(w)v$ is a word of length at most $2h$
satisfying the theorem.

Selection of pivot. Since $X$ consists of at least two words, there exists a
state $p$ such that at least two letters have defined the transition from it.
We choose $p$ to be a state with this property that is at the minimal distance
from the root state $r$, i.e., such that the length of the shortest word $w$
such that $\delta(r,w)=p$, is the smallest possible. Let $a,b\in\Sigma$ be two
letters with defined transitions going from $p$. Since each state on the path
from the root to $p$ has only one letter with a defined outgoing transition,
such a state $p$ is unique. For the literal automaton in Fig. 1(right), the
chosen state $p$ is $q_{3}$.

Filtering algorithm. Consider the following auxiliary algorithm having a word
$w\in\Sigma^{*}$ as the input. We perform steps for $i=1,2,\ldots$. In each
step, we keep a subset of _active_ states $S_{i}\subseteq Q$, and two words
$u_{i}$, $w_{i}$. At the beginning, $S_{1}=Q$, $u_{1}=\varepsilon$, and
$w_{1}=w$. In an $i$-th step, we have two cases.
(Case 1) If $p$ is active, then let $a$ be the first letter of $w_{i}$,
assuming $w_{i}$ is non-empty. We apply the transition of $a$ to $S_{i}$, and
let $S_{i+1}=\delta(S_{i},a)$ for the next iteration. Also, we move the first
letter from $w_{i}$ to the end of $u_{i}$, thus we set $u_{i+1}=u_{i}a$ and
$w_{i+1}$ to be such that $w_{i}=aw_{i+1}$.
(Case 2) If $p$ is not active, then let $y$ be the smallest letter, under some
fixed order on $\Sigma$ (the same for every step), that is non-mortal for
$S_{i}$, i.e., $\delta(S_{i},y)\neq\bot$. Such a letter always exists in a
literal automaton, as for every state we can find a non-mortal letter. We
apply $y$ to $S_{i}$, so $S_{i+1}=\delta(S_{i},y)$, and set $u_{i+1}=u_{i}y$
and $w_{i+1}=w_{i}$.
(Termination) If $w_{i+1}$ is empty or $u_{i+1}$ has length at least $h$, we
stop. The word $u_{i+1}$ is the output of the algorithm.

To see that the algorithm terminates, observe that at every step the length of
$u_{i}$ is increased by $1$, thus there are at most $h$ iterations.

For a word $z$, denote by $\alpha(z)$ the word $u_{i+1}$ obtained in the last
step of the algorithm. Note that $\delta(Q,u_{i})=S_{i}$ holds in every step.
Since every time we apply a letter that is non-mortal for the set of active
states, this word is non-mortal for $\mathrsfs{A}_{X}$. It has also a length
of at most $h$. Observe that for two different words $v_{1},v_{2}$, either the
words $\alpha(v_{1})$, $\alpha(v_{2})$ are different or they have length $h$.
Indeed, if they have a length smaller than $h$, then the algorithm terminates
when $w_{i+1}$ is empty. Consider the longest common prefix $v$ of $v_{1}$ and
$v_{2}$, so $v_{1}=vv^{\prime}_{1}$ and $v_{2}=vv^{\prime}_{2}$. The algorithm
executes in the same way up to the $|v|$-th time when Case 1 is applied. Then
it performs some iterations with Case 2, which do not decrease the length of
$w_{i}$. Finally, Case 1 must hold, and the algorithm applies the first
letters of $v^{\prime}_{1}$ and $v^{\prime}_{2}$. At this moment, the two
words constructed become different.

All-through-root word construction. Now, we show that there exists a word $w$
of length $\lceil\log_{2}hn\rceil$ such that, for every state $q\in Q$, either
the action of some prefix of $\alpha(w)$ maps $q$ to the root $r$ or the
action of $\alpha(w)$ is undefined for $q$, and the word $\alpha(w)$ is non-
mortal. Recall two letters $a,b\in\Sigma$ such that state $p$ has a defined
outgoing transition under both of them. Consider the set of the resulting
words $W=\\{\alpha(w)\mid w\in\\{a,b\\}^{\lceil\log_{2}hn\rceil}\\}$. If there
is at least one word of length $h$ in $W$, we are done. Otherwise, all words
in $W$ are of a length less than $h$, and there are at least $hn$ pairwise
distinct words. Then, by the pigeonhole principle, there is a subset
$W^{\prime}\subseteq W$ consisting of at least $n+1$ words of equal length.
Suppose for a contradiction that for every word $\alpha(w)\in W^{\prime}$,
there is a state $q_{\alpha(w)}$ such that
$\delta(q_{\alpha(w)},\alpha(w))\neq\bot$ and that is not mapped to $r$ by the
action of any prefix of $\alpha(w)$. Note that in a literal automaton of a
prefix code, every state except the root state has an ingoing transition for
exactly one letter. Thus for a pair $q$, $q^{\prime}$ of states and two words
$t$, $t^{\prime}$ of the same length, we can have
$\delta(q,t)=\delta(q^{\prime},t)\neq\bot$ only if some prefix of $t$ (or
$t^{\prime}$) has the action mapping $q$ (or $q^{\prime}$, respectively) to
the root state. Therefore, all states $q_{\alpha(w)}$ for $\alpha(w)\in
W^{\prime}$ are pairwise distinct, and we have at least $n+1$ such states.
This means that the number of states of $\mathrsfs{A}_{X}$ is larger than $n$,
which is a contradiction. Thus, we get a non-mortal word $\alpha(w)$ of length
at most $h$ with the property that every state $q\in Q$ with
$\delta(q,\alpha(w))\neq\bot$ is mapped to the root state by some prefix of
$\alpha(w)$.

Splitting the image. We consider the set $\delta(Q,\alpha(w))$ and split it
into two sets, one with specific states and the other one with logarithmic
size. Let $P\subseteq Q$ be the set of all states in the unique shortest path
from $r$ to $p$ excluding $p$ itself. For the literal automaton in Fig.
1(right), $P=\\{q_{1},q_{2}\\}$. The size of $P$ is at most $h$. Note that, by
the selection of $p$, for each state in $P$, exactly one letter has a defined
transition. Thus, the other set $Q\setminus P$ has the property that the
unique shortest path from $r$ to each state from $Q\setminus P$ contains $p$.
Note that $\delta(Q,\alpha(w))\cap(Q\setminus P)$ has up to
$\lceil\log_{2}hn\rceil$ states, since by the construction of $\alpha(w)$, at
most $|w|$ prefixes of $\alpha(w)$ have the action mapping some state to $p$
(when Case 1 holds).

Compressing the part in $P$. Denote by $R$ the image $\delta(Q,\alpha(w))$. We
are going to construct a word $v$ of length at most $h$ such that
$1\leq|\delta(P\cap R,v)|\leq\lceil\log_{2}h\rceil$. However, if $P\cap
R=\emptyset$, then we skip this phase and let $v=\varepsilon$.

Consider the following procedure constructing an auxiliary word $v$. We
perform steps $i=1,2,\ldots$, and in an $i$-th step keep a word $v_{i}$ and a
set $S_{i}$ of _active_ states. At the beginning, we set $v_{1}=\varepsilon$
and $S_{1}=R\cap P$. In an $i$-th step, we do the following. Let $\ell_{i}$ be
the shortest word mapping some active state from $P$ to $p$. We apply
$\ell_{i}$ to the set $S$ of active states and let
$S^{\prime}=\delta(S,\ell_{i})$. Let $\ell^{\prime}_{i}\in\\{a,b\\}$ be a
letter whose transition is undefined for at least half of the states in
$S^{\prime}\cap P$ (unless $S^{\prime}\cap P=\emptyset$). At least one of
these two letters have this property since all states in $P$ have only one
defined transition. We set $v_{i+1}=v_{i}\ell_{i}\ell^{\prime}_{i}$ and
$S_{i+1}=\delta(S^{\prime}\setminus\\{p\\},\ell^{\prime}_{i})$ for the next
step; note that we additionally remove $p$ from the set of active states. If
the length of $v_{i+1}$ is at least $h$ or $S_{i+1}=\emptyset$, we stop.
Otherwise, we proceed to the $(i+1)$-th step for $S_{i+1}\subset P$ of size at
most $\lfloor|S_{i}|/2\rfloor$.

Denote the word $v_{i+1}$ constructed at the last step by $v$. By the
construction, the word $\alpha(w)v$ is non-mortal, because after each step,
$p\in\delta(P\cap R,v_{i+1})$. The number of active states decreases at least
twice in every step, thus the number of performed steps is at most
$\lceil\log_{2}h\rceil$. Furthermore, in every step, exactly one active state
from $P$ is mapped to a state in $Q\setminus P$, since we use the shortest
word such $\ell_{i}$. This state is always $p$, which we remove from the
active states. The number of these removed states is at most
$\lceil\log_{2}h\rceil$ and we know that the other states from $R\cap P$ are
mapped to $\bot$ in some step, thus the cardinality of $\delta(P\cap R,v)$ is
at most $\lceil\log_{2}h\rceil$.

To bound the length of $v$, we observe that the sum of the lengths of words
$\ell_{i}\ell^{\prime}_{i}$ from every iteration cannot exceed $h$. It is
because every active state, if it is not mapped to $\bot$, is mapped by the
action of $\ell_{i}\ell^{\prime}_{i}$ to a state farther from the root by
$|\ell\ell^{\prime}_{i}|$. Thus, the sum of the lengths cannot exceed $h$.

Summary. It follows that the rank of $\alpha(w)v$ is at most
$\lceil\log_{2}hn\rceil+\lceil\log_{2}h\rceil$: Indeed, the states in $Q$ that
are mapped into the set $P$ by the action of $\alpha(w)$ are then mapped by
the action of $v$ to a set of cardinality at most $\lceil\log_{2}h\rceil$. All
the other states are mapped by the action of $\alpha(w)$ to a set of size at
most $\lceil\log_{2}hn\rceil$.

Finally, note that the word $\alpha(w)v$ can be found in polynomial time. In
particular, to find $\alpha(w)$, we check
$2^{\lceil\log_{2}hn\rceil}=\mathcal{O}(hn)$ different words, and every word
is processed in polynomial time by the auxiliary algorithm computing $\alpha$.

######  Corollary 3.37.

Let $\mathrsfs{A}_{X}$ be a partial literal automaton with $n$ states. If it
is synchronizing, its reset threshold is at most $\mathcal{O}(n\log^{3}n)$. If
the Cerny conjecture holds, then it is $\mathcal{O}(n\log^{2}n)$.

######  Proof 3.38.

If $|X|=1$ then the bound follows from Proposition 3.33. If $|X|\geq 2$, from
Theorem 3.35, we get a word $w$ of length $\mathcal{O}(n)$ and rank
$\mathcal{O}(\log n)$. Then we use Corollary 3.31 with $w$, which yields the
upper bound
$\mathcal{O}(n)+\mathcal{O}(n)\cdot\operatorname{rt}(\mathrsfs{B})$, where
$\mathrsfs{B}$ is an induced automaton with $\mathcal{O}(\log n)$ states. Then
we use upper bounds on the reset threshold of a complete DFA ([32, 33])
transferred to strongly connected partial DFAs by Theorem 3.26.

##  4 Lower Bounds for Properly Incomplete Automata

We conclude with observations for transferring lower bounds from the complete
case to the partial case. Of course, in general, this is trivial, since a
complete automaton is a special case of a partial one. On the other hand,
letters with all transitions undefined cannot be used for synchronization.
Hence we need to add a restriction to exclude these cases and see the effect
of usable incomplete transitions. A partial automaton is _properly incomplete_
if there is at least one letter whose transition is defined for some state and
is undefined for some other state.

For an automaton $\mathrsfs{A}$, let the length of the shortest words of rank
$r$ be called the _rank threshold_ $\operatorname{rt}(\mathrsfs{A},r)$. We
show that bounding the rank/reset threshold of a strongly connected properly
incomplete automaton is related to bounding the corresponding threshold of a
complete automaton. A general construction for this is the following.

######  Definition 4.1 (Duplicating automaton).

For a complete automaton $\mathrsfs{A}=(Q,\Sigma,\delta{A})$, we construct the
_duplicating automaton_ $\mathrsfs{A}^{\mathrm{D}}=(Q\cup
Q^{\prime},\Sigma\cup\\{\gamma\\},\delta_{\mathrsfs{A}^{\mathrm{D}}})$ as
follows. Assume that $Q=\\{q_{1},\ldots,q_{n}\\}$. Then
$Q^{\prime}=\\{q^{\prime}_{1},\ldots,q^{\prime}_{n}\\}$ is a set of fresh
states disjoint with $Q$ and $\gamma\notin\Sigma$ is a fresh letter. For all
$1\leq i\leq n$ and $a\in\Sigma$, we define:
$\delta_{\mathrsfs{A}^{\mathrm{D}}}(q_{i},a)=q_{i}$,
$\delta_{\mathrsfs{A}^{\mathrm{D}}}(q_{i},\gamma)=q^{\prime}_{i}$,
$\delta_{\mathrsfs{A}^{\mathrm{D}}}(q^{\prime}_{i},a)=\delta{A}(q_{i},a)$, and
$\delta_{\mathrsfs{A}^{\mathrm{D}}}(q^{\prime}_{i},\gamma)=\bot$.

The duplicating automaton turns out to be a partial DFA counterpart to the
recent Volkov’s construction of a complete DFA [37]. The duplicating automaton
$\mathrsfs{A}^{\mathrm{D}}$ has twice the number of states of $\mathrsfs{A}$
and is properly incomplete. Also, it is strongly connected if $\mathrsfs{A}$
is.

######  Proposition 4.2.

Let $\mathrsfs{A}=(Q,\Sigma,\delta{A})$ be a strongly connected complete
automaton. For all $1\leq r<n$, we have
$\operatorname{rt}(\mathrsfs{A}^{\mathrm{D}},r)=2\operatorname{rt}(\mathrsfs{A},r)$.

######  Proof 4.3.

It is easy to observe that if $\mathrsfs{A}$ is strongly connected, then so is
$\mathrsfs{A}^{\mathrm{D}}$.

Let $1\leq r<n$, and let $w$ be a shortest word of rank at most $r$ in
$\mathrsfs{A}^{\mathrm{D}}$. We observe that $w=\gamma a_{1}\gamma a_{2}\gamma
a_{3}\dots\gamma a_{k}$, for some letters $a_{i}\in\Sigma$. Indeed, the action
of $a_{i}a_{j}$ is the same as the action of $a_{i}$, thus two consecutive
letters from $\Sigma$ cannot occur in a shortest word. Also, $\gamma^{2}$
cannot occur, as it is a mortal word. There is no letter $a_{i}$ at the
beginning of $w$, because
$\delta_{\mathrsfs{A}^{\mathrm{D}}}(Q,a_{i}\gamma)=\delta_{\mathrsfs{A}^{\mathrm{D}}}(Q,\gamma)=Q^{\prime}$.
Finally, $w$ does not contain $\gamma$ at the end, because otherwise the rank
would be the same, i.e., for all $S\subseteq Q^{\prime}$, we have
$|\delta_{\mathrsfs{A}^{\mathrm{D}}}(S,a_{i}\gamma)|=|\delta_{\mathrsfs{A}^{\mathrm{D}}}(S,a_{i})|$.

We observe that the word $w^{\prime}=a_{1}a_{2}\dots a_{k}$ has rank $r$ in
$\mathrsfs{A}$. Indeed, $\delta_{\mathrsfs{A}^{\mathrm{D}}}(Q\cup
Q^{\prime},w)\subset Q$, and $q_{i}\in\delta_{\mathrsfs{A}^{\mathrm{D}}}(Q\cup
Q^{\prime},w)$ if and only if $q_{i}\in\delta{A}(Q,w^{\prime})$. Since $w$ is
a word of rank $r$ in $\mathrsfs{A}^{\mathrm{D}}$, so is $w^{\prime}$ in
$\mathrsfs{A}$. Thus
$\operatorname{rt}(\mathrsfs{A}^{\mathrm{D}},r)=|w|=2|w^{\prime}|\geq
2\operatorname{rt}(\mathrsfs{A},r)$.

Conversely, having a shortest word $w^{\prime}=a_{1}a_{2}\dots a_{k}$ of rank
$r$ in $\mathrsfs{A}$, we can construct $w=\gamma a_{1}\gamma a_{2}\gamma
a_{3}\dots\gamma a_{k}$ or rank $r$ in $\mathrsfs{A}^{\mathrm{D}}$, thus
$\operatorname{rt}(\mathrsfs{A}^{\mathrm{D}},r)\leq
2\operatorname{rt}(\mathrsfs{A},r)$.

From Proposition 4.2, it follows that we cannot expect a better upper bound on
the reset threshold of a properly incomplete strongly connected automaton than
$0.04135n^{3}+\mathcal{O}(n^{2})$, unless we can improve the best general
upper bound on the reset threshold of a complete automaton, which currently is
roughly $0.1654n^{3}+\mathcal{O}(n^{2})$ [32]. We can also show a lower bound
on the largest possible reset threshold, using the Rystsov’s construction of
automata with long shortest mortal words [27].

######  Proposition 4.4.

For every $n$, there exists a strongly connected properly incomplete $n$-state
automaton with the reset threshold $\frac{n^{2}-n}{2}$.

######  Proof 4.5.

Let $\mathrsfs{A}=(Q,\Sigma,\delta)$ be a strongly connected partial automaton
with only one state $r$ having undefined outgoing transitions for some letter,
and let $w$ be its shortest mortal word. Let $w=w^{\prime}a$, where
$a\in\Sigma$. Then $\delta(Q,w^{\prime})=\\{r\\}$. Moreover, since the
automaton is strongly connected, every prefix $w^{\prime\prime}$ of
$w^{\prime}$ of length smaller than $|w|-(|Q|-1)$ has the action mapping $Q$
to a set of size at least two; otherwise, there is a shorter word mapping $Q$
to $\\{r\\}$. Thus we get that $\mathrsfs{A}$ is synchronizing, and the length
of its shortest reset word is at least $|w|-(|Q|-1)-1=|w|-|Q|$. For every $n$,
Rystsov [27] constructed a strongly connected properly incomplete $n$-state
automaton with the only one state having undefined outgoing transitions. The
length of its shortest mortal word is equal to $\frac{n^{2}+n}{2}$. Thus we
get the lower bound of $\frac{n^{2}+n}{2}-n$ on the length of its shortest
reset word. It can be seen directly from the construction of the automaton
that this bound is tight.

## References

  * [1] Parvaneh Babari, Karin Quaas, and Mahsa Shirmohammadi.  Synchronizing data words for register automata.  In MFCS, pages 15:1–15:15, 2016.
  * [2] Marie-Pierre Béal, Eugen Czeizler, Jarkko Kari, and Dominique Perrin.  Unambiguous automata.  Mathematics in Computer Science, 1(4):625–638, 2008.
  * [3] M. Berlinkov.  On Two Algorithmic Problems about Synchronizing Automata.  In Developments in Language Theory, LNCS, pages 61–67. Springer, 2014.
  * [4] M. Berlinkov and M. Szykuła.  Algebraic synchronization criterion and computing reset words.  Information Sciences, 369:718–730, 2016.
  * [5] J. Berstel, D. Perrin, and C. Reutenauer.  Codes and Automata.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009.
  * [6] M. T. Biskup and W. Plandowski.  Shortest synchronizing strings for Huffman codes.  Theoretical Computer Science, 410(38-40):3925–3941, 2009.
  * [7] V. Bruyère.  On maximal codes with bounded synchronization delay.  Theoretical Computer Science, 204(1):11–28, 1998.
  * [8] J. Černý.  Poznámka k homogénnym eksperimentom s konečnými automatami.  Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208–216, 1964.  In Slovak.
  * [9] Dmitry Chistikov, Pavel Martyugin, and Mahsa Shirmohammadi.  Synchronizing automata over nested words.  Journal of Automata, Languages and Combinatorics, 24(2-4):219–251, 2019.
  * [10] Laurent Doyen, Line Juhl, Kim Guldstrand Larsen, Nicolas Markey, and Mahsa Shirmohammadi.  Synchronizing words for weighted and timed automata.  In FSTTCS, pages 121–132, 2014.
  * [11] Laurent Doyen, Thierry Massart, and Mahsa Shirmohammadi.  Robust Synchronization in Markov Decision Processes.  In CONCUR, pages 234–248, 2014.
  * [12] Laurent Doyen, Thierry Massart, and Mahsa Shirmohammadi.  The complexity of synchronizing Markov decision processes.  J. Comput. Syst. Sci., 100:96–129, 2019.
  * [13] D. Eppstein.  Reset sequences for monotonic automata.  SIAM Journal on Computing, 19:500–510, 1990.
  * [14] Tero Harju and Dirk Nowotka.  On unique factorizations of primitive words.  Theor. Comput. Sci., 356(1-2):186–189, 2006.
  * [15] J. Hopcroft.  An $n\log n$ algorithm for minimizing states in a finite automaton.  In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, 1971.
  * [16] David A Huffman.  A method for the construction of minimum-redundancy codes.  Proceedings of the IRE, 40(9):1098–1101, 1952.
  * [17] B. Imreh and M. Steinby.  Directable nondeterministic automata.  Acta Cybern., 14(1):105–115, 1999.
  * [18] J. Kari.  A counter example to a conjecture concerning synchronizing word in finite.  EATCS Bulletin, 73:146–147, 2001.
  * [19] J. Kari.  Synchronizing finite automata on Eulerian digraphs.  Theoretical Computer Science, 295(1-3):223–232, 2003.
  * [20] Jarkko Kari, Andrew Ryzhikov, and Anton Varonka.  Words of minimum rank in deterministic finite automata.  In Developments in Language Theory - 23rd International Conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, Proceedings, pages 74–87, 2019.
  * [21] S. Kiefer and C. Mascle.  On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words.  In STACS, LIPIcs, 2019.
  * [22] Kim Guldstrand Larsen, Simon Laursen, and Jiří Srba.  Synchronizing strategies under partial observability.  In International Conference on Concurrency Theory, pages 188–202. Springer, 2014.
  * [23] B. K. Natarajan.  An algorithmic approach to the automated design of parts orienters.  In Foundations of Computer Science, 27th Annual Symposium on, pages 132–142, 1986.
  * [24] J.-E. Pin.  Utilisation de l’algèbre linéaire en théorie des automates.  In Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées II, AFCET, pages 85–92, 1978.  In French.
  * [25] 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.
  * [26] I. K. Rystsov.  Polynomial complete problems in automata theory.  Information Processing Letters, 16(3):147–151, 1983.
  * [27] I. K. Rystsov.  Reset words for commutative and solvable automata.  Theoretical Computer Science, 172(1-2):273–279, 1997.
  * [28] A. Ryzhikov.  Mortality and synchronization of unambiguous finite automata.  In Combinatorics on Words - 12th International Conference, WORDS 2019, Loughborough, UK, September 9-13, 2019, Proceedings, pages 299–311, 2019.
  * [29] A. Ryzhikov and M. Szykuła.  Finding Short Synchronizing Words for Prefix Codes.  In Igor Potapov, Paul Spirakis, and James Worrell, editors, MFCS 2018, volume 117 of LIPIcs, pages 21:1–21:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
  * [30] S. Sandberg.  Homing and synchronizing sequences.  In Model-Based Testing of Reactive Systems, volume 3472 of LNCS, pages 5–33. Springer, 2005.
  * [31] H. Shabana.  Exact synchronization in partial deterministic automata.  Journal of Physics: Conference Series, 1352:012047, 2019.
  * [32] 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.
  * [33] 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.
  * [34] N. F. Travers and J. P. Crutchfield.  Exact Synchronization for Finite-State Sources.  Journal of Statistical Physics, 145(5):1181–1201, 2011.
  * [35] L. Trevisan.  Notes on state minimization.  https://people.eecs.berkeley.edu/~luca/cs172-07/notemindfa.pdf, 2007\.
  * [36] M. V. Volkov.  Synchronizing automata and the C̆erný conjecture.  In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11–27. Springer, 2008.
  * [37] M. V. Volkov.  Slowly synchronizing automata with idempotent letters of low rank.  Journal of Automata, Languages and Combinatorics, 24(2–4):375–386, 2019.
  * [38] Vojtech Vorel.  Subset synchronization and careful synchronization of binary finite automata.  Int. J. Found. Comput. Sci., 27(5):557–578, 2016.
  * [39] C. M. Weinbaum.  Unique subwords in nonperiodic words.  Proceedings of the American Mathematical Society, 109(3):615–619, 1990.