# Cornering Robots to Synchronize a DFA

Peter Bradshaw  Department of Mathematics, University of Illinois Urbana-
Champaign<EMAIL_ADDRESS>,  Alexander Clow  Department of Mathematics,
Simon Fraser University<EMAIL_ADDRESS>and  Ladislav Stacho
Department of Mathematics, Simon Fraser University<EMAIL_ADDRESS>
###### Abstract.

This paper considers the existence of short synchronizing words in
deterministic finite automata (DFAs). In particular, we define a general
strategy, which we call the _cornering strategy_ , for generating short
synchronizing words in well-structured DFAs. We show that a DFA is
synchronizable if and only if this strategy can be applied.

Using the cornering strategy, we prove that all DFAs consisting of $n$ points
in $\mathbb{R}^{d}$ with bidirectional connected edge sets in which each edge
$(\mathbf{x},\mathbf{y})$ is labeled $\mathbf{y}-\mathbf{x}$ are
synchronizable. We also give sufficient conditions for such DFAs to have
synchronizing words of length at most $(n-1)^{2}$ and thereby satisfy Černý’s
conjecture. Using similar ideas, we generalise a result of Ananichev and
Volkov [1] from monotonic automata to a wider class of DFAs admitting well-
behaved partial orders. Finally, we consider how the cornering strategy can be
applied to the problem of simultaneously synchronizing a DFA $G$ to an initial
state $u$ and a DFA $H$ to an initial state $v$. We do not assume that DFAs
$G$ and $H$ or states $u$ and $v$ are related beyond sharing the same edge
labels.

We thank Tom Shermer and Jan Manuch for insightful initial discussions on this
problem, particularly as they pertain to disjoint DFAs and difference DFAs in
$\mathbb{R}^{2}$. This project was partially funded by NSF RTG grant
DMS-1937241, and by NSERC through Discovery Grant R611368.

##  1\. Introduction

A deterministic finite automaton (or DFA) $G=(V,E,\psi)$ is a finite directed
multigraph $(V,E)$, possibly with loops, and an edge labeling
$\psi:E\rightarrow\Psi$ using some alphabet $\Psi$, such that for all
$\alpha\in\Psi$ and $v\in V$, there exists a unique edge $(v,w)\in E$
satisfying $\psi(v,w)=\alpha$. It is sometimes convenient to suppose our DFA
has a current state, that is, a specific vertex $u\in V$ which we identify as
the current state. When $u$ is the current state of $G$, we write
$G=(V,E,\psi,u)$ or $G_{u}$. We let $\Psi^{*}$ be the set of all words
generated by the alphabet $\Psi$.

Given a state $u\in V$ and an input word $\sigma=\alpha_{1}\dots\alpha_{k}$,
where $\alpha_{1},\dots,\alpha_{k}\in\Psi$, the state resulting from the input
$\sigma$ is the unique vertex $u(\sigma)=:v$ for which there is a directed
walk $W=u,w_{1},\dots,w_{k-1},v$ satisfying
$\psi(u,w_{1})=\alpha_{1},\dots,\psi(w_{i},w_{i+1})=\alpha_{i+1},\dots,\psi(w_{k-1},v)=\alpha_{k}$.
For example, given the DFA depicted in Figure 1, if the current state is $u$
and the input is the word $\sigma=$ “green (lightly dotted), green (lightly
dotted)”, then $u(\sigma)=v$. When $G$ has current state $u$, we let
$G(\sigma)=(V,E,\psi,u(\sigma))$. Given a walk $W$ with an edge sequence
$(e_{1},\dots,e_{t})$, we often write $\psi(W)=\psi(e_{1})\dots\psi(e_{t})$.

DFAs give a framework for representing a given machine, along with possible
transitions between the machine’s states. In this framework, input words using
the alphabet $\Psi$ correspond to inputs for the given machine, while each
vertex in the DFA corresponds to a possible state of the machine. For
convenience, one can represent a machine with current state $u$ as a DFA with
a robot standing on the vertex $u$, so that inputting the word $\sigma$ to the
machine commands the robot at $u$ to follow the walk $W$ beginning at $u$ with
$\psi(W)=\sigma$.

When using a machine with multiple possible states, it is often convenient to
have a command that resets the machine from any state to some initial state.
For instance, a machine’s current state may become unknown to a user, say
after the machine receives accidental or random inputs. In these cases, a
reset command that updates the machine to a prescribed state allows a user to
regain control over the machine state and execute meaningful commands. Given a
DFA $G=(V,E,\psi)$ and a vertex $z\in Z$, if there exists a word $\sigma$ such
that $v(\sigma)=z$ for all $v\in V$, then we say that $\sigma$ is a _$z$
-synchronizing word_. If $G$ has a $z$-synchronizing word, then we say $G$ is
$z$-synchronizable. If the choice of $z$ is clear from context or is not
relevant to a specific application, then we say that $\sigma$ is a
synchronizing word in $G$ and that $G$ is synchronizable.

$v$$u$

Figure 1. An example of a DFA with no loops drawn and edges with the same
label receiving the same colour.

This formulation of synchronizing words was first considered in the early
1960s, most notably by Černý in [3], with the notion first appearing slightly
earlier in [9, 10, 11]. In [3] Černý constructed, for each $n$, a DFA of order
$n$ whose shortest synchronizing word has length exactly $(n-1)^{2}$. This
construction led Černý to the following conjecture.

######  Conjecture 1.1 (Černý’s conjecture [3]).

If $G$ is a synchronizable DFA of order $n$, then $G$ has a synchronizing word
$\sigma$ of length $|\sigma|\leq(n-1)^{2}$.

Since initially being proposed, Černý’s conjecture has become a central open
question in automata theory. Until recently, the most notable progress on
Černý’s conjecture came from work by Pin [14] and Frankl [7], who showed that
each synchronizable DFA of order $n$ has a synchronizing word of length at
most $(n^{3}-n)/6$. The current best upper bound on the length of a shortest
synchronizing word in a synchronizable DFA of order $n$ is
$(\frac{7}{48}+\frac{15625}{798768})n^{3}+o(n^{3})$, as shown by Shitov [15].
Shitov’s improvement builds off two earlier papers by Szykuła [16] and
Trahtman [17]. Thus, for a general synchronizable DFA, the best upper bound
remains far from Černý’s conjecture, despite significant effort.

Notably, Černý’s conjecture has also been proven for some specific classes of
DFAs. These include Eulerian DFAs [8], DFAs which admit a Hamiltonian cycle in
which every edge has the same label [4], and DFAs which admit particular
orderings on vertices that are preserved under the action of any word [1, 2,
5]. For more on Černý’s conjecture and synchronizing DFAs more broadly, we
recommend the 2022 survey by Volkov [18].

Our paper contributes to the literature by defining an intuitive strategy for
generating short synchronizing words in well-structured DFAs, as well as
exploring examples of how this strategy can be applied. We call our strategy
the cornering strategy.

In Section 2 we establish the preliminaries necessary for the rest of the
paper, including definitions and examples. The cornering strategy is outlined
in Section 3 and is proven using elementary means. Next, in Section 4, we
demonstrate the power of the cornering strategy by using it to prove that a
large class of DFAs, which appear naturally in video games and as models for
robotic movement, contain short synchronizing words. Moreover, we give
conditions for these DFAs to satisfy Černý’s conjecture. In Section 5, we
explore a related, although distinct, class of DFAs which we call partially
ordered DFAs. A particularly nice class of these DFAs appears in prior work by
Ananichev and Volkov [1] by the name of _monotonic automata_ and is related to
star-free languages [2]. The main result of Section 5 is a generalization of
Theorem 1 of [1] from monotonic automata to partially ordered DFAs. Finally,
Section 6 focuses on generating a word $\sigma$ which is $u$-synchronizing in
a DFA $G$ and $v$-synchronizing in a DFA $H$. This problem is natural given
situations where two different models of machines receive radio commands over
the same channel.

##  2\. Preliminaries

This section establishes definitions and notation which are vital to the
remainder of the paper.

We say that a DFA is connected if and only if its underlying directed
multigraph is strongly connected. For an example of a DFA that is not
connected, see Figure 1. For an example of a connected DFA, see Figure 2.

It is sometimes useful to have an even stronger notion of connectivity in a
DFA. To this end, we say a DFA $G=(V,E,\psi)$ is bidirectional connected if
and only if $G$ is connected and for every edge $(u,v)\in E$, there exists an
edge $(v,u)\in E$. For an example of a bidirectional connected DFA, consider a
DFA with only loop edges.

Given a DFA $G=(V,E,\psi)$ and a vertex pair $u,v\in V$, we write
$\operatorname{dist}(u,v)$ for the number of edges in a shortest directed path
from $u$ to $v$. That is, $\operatorname{dist}(u,v)$ is the ordinary directed
graph distance. Notice that if $G$ is a bidirectional connected DFA, then for
all $u,v$ in $V$, $\operatorname{dist}(u,v)=\operatorname{dist}(v,u)$.

A _difference DFA in $\mathbb{R}^{d}$_ is defined as a DFA $(V,E,\psi)$
satisfying the following properties:

  1. (1)

$V$ is a finite subset of $\mathbb{R}^{d}$;

  2. (2)

The alphabet $\Psi$ is defined by
$\Psi=\\{\mathbf{u}-\mathbf{v}:\mathbf{u},\mathbf{v}\in
V\\}\setminus\\{\mathbf{0}\\}$;

  3. (3)

For each distinct pair $\mathbf{u},\mathbf{v}\in V$, if
$(\mathbf{u},\mathbf{v})\in E$, then
$\psi(\mathbf{u},\mathbf{v})=\mathbf{v}-\mathbf{u}$;

  4. (4)

For each distinct pair $\mathbf{u},\mathbf{v}\in V$, if
$(\mathbf{u},\mathbf{v})\notin E$, then there is a loop
$e=(\mathbf{u},\mathbf{u})\in E$ such that $\psi(e)=\mathbf{v}-\mathbf{u}$.

We note that condition (4) is required for $G$ to be a DFA, given that for
each symbol $\alpha$ in the alphabet and each vertex $v\in V(G)$, there is an
edge leaving $v$ with label $\alpha$. Notice that the edge set of a difference
DFA in $\mathbb{R}^{d}$ need not be bidirectional. For an example of a
difference DFA, see Figure 2.

Difference DFAs in $\mathbb{R}^{d}$ are often natural models for movement in
real life and simulated spaces, and difference DFAs in $\mathbb{R}^{2}$ and
$\mathbb{R}^{3}$ can be used to model the movement of robots and simple
machines. For example, if we imagine a delivery robot in a warehouse, a
universal command that returns the robot from any location to the loading dock
or charging port corresponds to a synchronizing word in a difference DFAs in
$\mathbb{R}^{2}$. This kind of application is particularly useful in the
context of simple machines, which may not be able to relay any kind of data to
the controller about their current location or state.

By considering a group $X$ rather than a vector space $\mathbb{R}^{d}$, we can
analogously define a difference DFA in $X$. A DFA whose vertices are group
elements can model movement in more kinds of geometry than just real space.
For example a difference DFA in $(\mathbb{R}/\mathbb{Z})\times\mathbb{R}$ can
act as a model for movement on the surface of a cylinder while a difference
DFA in $(\mathbb{R}/\mathbb{Z})\times(\mathbb{R}/\mathbb{Z})$ can act as a
model for movement on the surface of a torus. Many classical two-dimensional
video games employ one of these two movement models, which are colloquially
called wraparound. For example, PacMan and Asteroids model their movement on a
torus, while the popular Civilization series model its game world as the
surface of a finite cylinder. However, for the purposes of this paper we
restrict ourselves to considering difference DFAs in $\mathbb{R}^{d}$.

Figure 2. A difference DFA $G$ with a vertex set $V\subseteq\mathbb{R}^{2}$
with no loops drawn and edges with the same label receiving the same colour.
In this example, the vertex set $V$ is equal to the set of integer points in
the rectangle $[0,4]\times[0,2]$.

Given a function $f:\Psi^{*}\rightarrow\\{-1,1\\}$ and a DFA $G=(V,E,\psi)$,
we extend the definition of $f$ so that $f(W):=f(\psi(W))$ for each directed
walk $W$ in $G$. Then, we say that a walk $W$ in $G$ is $f$-positive if
$f(W)=1$ and $f$-negative if $f(W)=-1$. When the choice of $f$ is clear from
context, we simply say that $W$ is positive or negative. Similarly, we say a
word $\sigma$ is $f$-positive if $f(\sigma)=1$ and $f$-negative if
$f(\sigma)=-1$.

We write $\operatorname{dist}^{+}_{f}(u,v)$ for the length of a shortest
$f$-positive walk from $u$ to $v$ in $G$. Similarly, we write
$\operatorname{dist}^{-}_{f}(u,v)$ for the length of a shortest $f$-negative
walk from $u$ to $v$ in $G$. Note that
$\operatorname{dist}^{+}_{f}(u,u)=\operatorname{dist}^{-}_{f}(u,u)=0$ for each
$u\in V$. Furthermore, if there is no $f$-positive walk from $u$ to $v$, then
we write $\operatorname{dist}^{+}_{f}(u,v)=\infty$, and if there is no
$f$-negative walk from $u$ to $v$, then we write
$\operatorname{dist}^{-}_{f}(u,v)=\infty$.

Next, we say that $z\in V$ is an $f$-corner in $G$ if
$\operatorname{dist}^{+}_{f}(u,z)<\operatorname{dist}^{+}_{f}(z,u)$ for all
$u\in V\setminus\\{z\\}$. When $f$ is clear from context, we say that $z$ is a
_corner_. For some examples of corners, see Figure 3. In particular, notice
that $v$ is an $f$-corner, because for all vertices there is a shortest path
to $v$ which is $f$-positive, whereas no path leaving $v$ is $f$-positive.
Furthermore, while not every $x\in V\setminus\\{u\\}$ has a shortest path to
$u$ that is $f$-positive, one can still verify that
$\operatorname{dist}^{+}_{g}(x,u)<\operatorname{dist}^{+}_{g}(u,x)$ for all
$x\in V\setminus\\{u\\}$. Therefore, $u$ is a $g$-corner. Also notice that $u$
is not an $f$-corner, and $v$ is not a $g$-corner.

$u$$v$

Figure 3. A connected DFA with an $f$-corner $v$ and a $g$-corner $u$. Here,
$f:\Psi^{*}\rightarrow\\{-1,1\\}$ is a function in which a word is positive if
and only if it begins with red (dashed) or blue (solid), and
$g:\Psi^{*}\rightarrow\\{-1,1\\}$ is a function in which a word is positive if
and only if it does not begin with red (dashed).

##  3\. Cornering Robots

This section focuses on the cornering strategy, which is described in the
proof of Theorem 3.1. As a result, Theorem 3.1 can be viewed as a summary of
the necessary conditions for applying the cornering strategy, as well as an
upper bound on the length of the resulting synchronizing word. Afterward, in
Theorem 3.2, we prove that a DFA is $x$-synchronizable if and only if there
exists a function $f:\Psi^{*}\rightarrow\\{-1,1\\}$ such that $x$ is an
$f$-corner.

######  Theorem 3.1.

Let $G=(V,E,\psi)$ be a DFA of order $n$, and let
$f:\Psi^{*}\rightarrow\\{-1,1\\}$. If $x\in V$ is $f$-corner of $G$, then $G$
has an $x$-synchronizing word of length at most $\frac{(n-1)d(d+1)}{2}$, where
$d=\max_{u\in V}\operatorname{dist}^{+}_{f}(u,x)$

###### Proof.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$ with an alphabet $\Psi$,
and let $f:\Psi^{*}\rightarrow\\{-1,1\\}$. Suppose there exists an $f$-corner
$x$ in $G$ such that $d=\max_{u\in V}\operatorname{dist}^{+}_{f}(u,x)$. For
all $u\in V$, we let $r_{u}=(V,E,\psi,u)$, and we imagine that $r_{u}$ is a
robot on vertex $u$. Throughout the proof, we pass commands to each robot
$r_{u}$, and as a result, the state of $r_{u}$ changes. We construct an
$x$-synchronizing word of length at most $\frac{(n-1)d(d+1)}{2}$ by passing
commands from $\Psi^{*}$ to the robots on $G$ with the goal of moving every
robot to $x$.

First, given a fixed vertex $u\in V$, we describe a procedure for constructing
a word $\tau_{u}$ for which $x(\tau_{u})=u(\tau_{u})=x$. In order to construct
the word $\tau_{u}$, we imagine that a robot $r_{1}$ occupies $u$ and that a
second robot $r_{2}$ occupies $x$. Our goal is to construct a word $\tau_{u}$
so that when $\tau_{u}$ is passed to $r_{1}$ and $r_{2}$, both robots move to
$x$. We construct $\tau_{u}$ over many iterations, as follows.

Iterating through $i=1,\dots,d$ in order, we define a word $\sigma_{i}$ that
we pass to $r_{1}$ and $r_{2}$ as follows. If $i$ is odd, then we let $W_{i}$
be a shortest $f$-positive walk from the current vertex occupied by $r_{1}$ to
the vertex $x$. If $i$ is even, then we let $W_{i}$ be a shortest $f$-positive
walk from the current vertex occupied by $r_{2}$ to the vertex $x$. In both
cases, we let $\sigma_{i}=\psi(W_{i})$. Notice that if $r_{1}$ and $r_{2}$
both occupy vertex $x$ after iteration $i$, then for all $j>i$, $W_{j}$ is an
empty walk, implying that $\sigma_{j}$ is the empty word. After iterating
through $i=1,\dots,d$ we stop. For technical reasons, we also imagine that
$i=0$ before we define $\sigma_{1}$, and that we have an iteration
corresponding to $i=0$ in which the empty word $\sigma_{0}=\emptyset$ is
passed to the robots. Finally, we write
$\tau_{u}=\sigma_{0}\sigma_{1}\dots\sigma_{d}$, so that $\tau_{u}$ is the
entire word that is passed to $r_{1}$ and $r_{2}$ over all iterations.

We claim that after receiving $\tau_{u}$, robots $r_{1}$ and $r_{2}$ both
occupy $x$. To prove this claim, we show by induction that after iteration
$i$, the following holds:

  * •

If $i$ is even, then after $\sigma_{0}\dots\sigma_{i}$ is passed, the shortest
$f$-positive walk from the vertex currently occupied by $r_{1}$ to the vertex
$x$ has a length of at most $d-i$, and $r_{2}$ occupies $x$.

  * •

If $i$ is odd, then after $\sigma_{0}\dots\sigma_{i}$ is passed, $r_{1}$
occupies $x$, and a shortest $f$-positive walk from the vertex currently
occupied by $r_{2}$ to the vertex $x$ has a length of at most $d-i$.

When $i=d$, the statement implies that both $r_{1}$ and $r_{2}$ occupy $x$.

To prove the statement, consider a value $0\leq i\leq d$. For our base case,
when $i=0$, we observe that $r_{2}$ occupies $x$, and we write $u$ for the
vertex occupied by $r_{1}$. Then, our theorem’s hypothesis implies that
$\operatorname{dist}_{f}^{+}(u,x)\leq d$, completing the base case. Next,
suppose that $i\geq 1$ and that $i$ is odd. By our induction hypothesis, at
the beginning of iteration $i$, $r_{2}$ occupies $x$, and a shortest
$f$-positive walk from the vertex occupied by $r_{1}$ to $x$ has length at
most $d-(i-1)=d-i+1$. Hence, the word $\sigma_{i}$ has length $|W_{i}|\leq
d-i+1$. Finally, we write $u^{\prime}$ for the vertex that $r_{2}$ occupies
after receiving the word $\sigma_{i}$, and we observe that
$\operatorname{dist}^{+}_{f}(x,u^{\prime})\leq|W_{i}|\leq d-i+1$. Since $x$ is
an $f$-corner,
$\operatorname{dist}_{f}^{+}(u^{\prime},x)<\operatorname{dist}_{f}^{+}(x,u^{\prime})\leq
d-i+1$. Hence, $\operatorname{dist}_{f}^{+}(u^{\prime},x)\leq d-i$.
Furthermore, by definition of $\sigma_{i}$, $r_{1}$ moves to $x$ after
receiving the word $\sigma_{i}$. Therefore, at the end of iteration $i$,
$r_{1}$ occupies $x$, and a shortest $f$-positive walk from the vertex
occupied by $r_{2}$ to the vertex $x$ has length at most $d-i$, as claimed.
When $i$ is even, the proof is similar, with $r_{1}$ and $r_{2}$ switched.
This completes induction.

We observe that the length of the word
$\tau_{u}=\sigma_{1}\sigma_{2}\dots\sigma_{d}$ passed to the robots $r_{1}$
and $r_{2}$ throughout all iterations is at most
$d+(d-1)+\dots+1=\frac{d(d+1)}{2}$.

Now, we construct an $x$-synchronizing word $\tau$ in $G$. First, we write
$r_{x}$ for the robot that occupies $x$. We say that a robot $r$ in $G$ is
_synchronized_ if $r$ and $r_{x}$ both occupy $x$. Initially, exactly $n-1$
robots on $G$ are not synchronized.

We construct $\tau$ as follows. We initialize $\tau=\emptyset$. Then, while
there exists a robot $r$ that occupies a vertex $u\in V\setminus\\{x\\}$, we
define a word $\tau_{u}$ of the length at most $\frac{d(d+1)}{2}$ that moves
both $r$ and $r_{x}$ to $x$, as described above. We pass $\tau_{u}$ to all
robots and update $\tau\leftarrow\tau\tau_{u}$. We observe that after passing
$\tau_{u}$, the number of robots which are not synchronized decreases by at
least $1$. Since $n-1$ robots are initially not synchronized, it follows that
we can construct an $x$-synchronizing word $\tau$ as a concatenation of at
most $n-1$ words $\tau_{u}$, each of length at most $\frac{d(d+1)}{2}$.
Therefore, we find an $x$-synchronizing word of length at most
$\frac{(n-1)d(d+1)}{2}$, completing the proof. ∎

Thus, we have shown that the existence of an $f$-corner is a sufficient
condition for a DFA to be synchronizable. Now, we show that the existence of
an $f$-corner is also a necessary condition for a DFA to be synchronizable.

######  Theorem 3.2.

Let $G=(V,E,\psi)$ be a DFA. For each $x\in V$, $G$ is $x$-synchronizable if
and only if there exists an $f:\Psi^{*}\rightarrow\\{-1,1\\}$ such that $x$ is
an $f$-corner.

###### Proof.

Let $G=(V,E,\psi)$ be a DFA and $x\in V$ a vertex. We begin by noting that if
there exists a $f:\Psi^{*}\rightarrow\\{-1,1\\}$ such that $x$ is an
$f$-corner, then Theorem 3.1 implies that $G$ is $x$-synchronizable.

Suppose, on the other hand, that $G$ is $x$-synchronizable. Let $\tau$ be an
$x$-synchronizing word. Let $f:\Psi^{*}\rightarrow\\{-1,1\\}$ be the function
defined by $f(\sigma)=1$ if and only if $\sigma$ is an $x$-synchronizing word.
Then, $f(\tau)=1$. As $\tau$ is $x$-synchronizing, $u(\tau)=x$ for all $u\in
V$; thus, $\operatorname{dist}_{f}^{+}(u,x)$ is finite. On the other hand, for
each $x$-synchronizing word $\sigma$ and each $u\in V\setminus\\{x\\}$,
$x(\sigma)=x\neq u$, implying that $\operatorname{dist}_{f}^{+}(x,u)=\infty$.
Thus, $\operatorname{dist}_{f}^{+}(u,x)<\operatorname{dist}_{f}^{+}(x,u)$ for
all $u\neq x$, implying $x$ is an $f$-corner. This completes the proof. ∎

##  4\. Difference DFAs in $\mathbb{R}^{d}$

The aim of this section is to prove Theorem 4.3 and Theorem 4.5. That is, we
show that each bidirectional connected difference DFA in $\mathbb{R}^{d}$ is
synchronizable. Furthermore, we prove that if every vertex in a bidirectional
connected difference DFA $G$ on $n$ elements has $\Omega(\sqrt{n})$ out-
neighbours, then the synchronizing word for which results from our
construction has the length $O(n^{2})$. In doing so, we show that if every
vertex of $G$ in $\mathbb{R}^{d}$ has at least $3\sqrt{\frac{n}{2}}-1$ out-
neighbours, then $G$ satisfies Černý’s conjecture.

First, we establish several properties about finite sets of points in
$\mathbb{R}^{d}$. Our goal is to show that for every bidirectional connected
difference DFA in $\mathbb{R}^{d}$, $G$, there exists a function
$f:\Psi^{*}\rightarrow\\{-1,1\\}$, such that $G$ has an $f$-corner.

The following lemma is often called the Obtuse Angle Criterion.

######  Lemma 4.1 ([13, Theorem 5.1.1]).

Let $C\subseteq\mathbb{R}^{d}$ be a convex set, and let $\mathbf{y}\not\in C$.
Then, $\mathbf{x}^{*}\in C$ is the closest point in $C$ to $\mathbf{y}$ if and
only if
$(\mathbf{y}-\mathbf{x}^{*})\boldsymbol{\cdot}(\mathbf{x}-\mathbf{x}^{*})\leq
0$ for all $\mathbf{x}\in C$.

######  Lemma 4.2.

If $S\subset\mathbb{R}^{d}$ is a non-empty finite set, then there exists a
point $\mathbf{z}\in S$ and a nonzero vector $\mathbf{a}$ such that

$\mathbf{a}\boldsymbol{\cdot}\mathbf{x}<\mathbf{a}\boldsymbol{\cdot}\mathbf{z}$

for all $\mathbf{x}\neq\mathbf{z}$ in the convex hull of $S$.

###### Proof.

We induct on $S$. If $|S|=1$, so that $S=\\{\mathbf{z}\\}$, then we let
$\mathbf{a}$ be any nonzero vector, and we are done.

Now, suppose that $|S|>1$. Let $S^{\prime}=S\setminus\\{\mathbf{s}\\}$ for
some $\mathbf{s}\in S$. Let $\mathbf{z}^{\prime},\mathbf{a}^{\prime}$ be given
for $S^{\prime}$ by the induction hypothesis. If $\mathbf{s}$ is in the convex
hull of $S^{\prime}$, then we let $\mathbf{a}=\mathbf{a}^{\prime}$,
$\mathbf{z}=\mathbf{z}^{\prime}$, and we are done. Otherwise, suppose that
$\mathbf{s}$ does not belong to the convex hull of $S^{\prime}$.

We let $\mathbf{x}^{*}$ be the point in the convex hull of $S^{\prime}$ which
is closest to $\mathbf{s}$ (by the Euclidean norm), which exists as the convex
hull of $S^{\prime}$ is closed. We claim that if $\mathbf{z}=\mathbf{s}$ and
$\mathbf{a}=\mathbf{z}-\mathbf{x}^{*}$, then $\mathbf{a}$ and $\mathbf{z}$
satisfy the theorem.

We first consider a point $\mathbf{x}$ in the convex hull of $S^{\prime}$, and
we show that
$\mathbf{a}\boldsymbol{\cdot}\mathbf{x}<\mathbf{a}\boldsymbol{\cdot}\mathbf{z}$.
As $\mathbf{x}^{*}$ is closest to $\mathbf{z}$, Lemma 4.1 tells us that

$\mathbf{a}\boldsymbol{\cdot}(\mathbf{x}-\mathbf{x}^{*})=(\mathbf{z}-\mathbf{x}^{*})\boldsymbol{\cdot}(\mathbf{x}-\mathbf{x}^{*})\leq
0.$

Hence,
$\mathbf{a}\boldsymbol{\cdot}\mathbf{x}\leq\mathbf{a}\boldsymbol{\cdot}\mathbf{x}^{*}$,
so it is enough to show that
$\mathbf{a}\boldsymbol{\cdot}\mathbf{x}^{*}<\mathbf{a}\boldsymbol{\cdot}\mathbf{z}$.
For this, we observe that since $\mathbf{z}$ is not in the convex hull of
$S^{\prime}$, $\mathbf{z}-\mathbf{x}^{*}\neq\mathbf{0}$, and thus

$0<\|\mathbf{z}-\mathbf{x}^{*}\|^{2}=\mathbf{z}\boldsymbol{\cdot}\mathbf{z}+\mathbf{x}^{*}\boldsymbol{\cdot}\mathbf{x}^{*}-2\mathbf{z}\boldsymbol{\cdot}\mathbf{x}^{*}.$

Hence,

$\mathbf{z}\boldsymbol{\cdot}\mathbf{x}^{*}-\mathbf{x}^{*}\boldsymbol{\cdot}\mathbf{x}^{*}<\mathbf{z}\boldsymbol{\cdot}\mathbf{z}-\mathbf{x}^{*}\boldsymbol{\cdot}\mathbf{z},$

which simplifies to

$\mathbf{(}\mathbf{z}-\mathbf{x}^{*})\boldsymbol{\cdot}\mathbf{x}^{*}<(\mathbf{z}-\mathbf{x}^{*})\boldsymbol{\cdot}\mathbf{z},$

or equivalently,

$\mathbf{a}\boldsymbol{\cdot}\mathbf{x}^{*}<\mathbf{a}\boldsymbol{\cdot}\mathbf{z}.$

Now, consider a point $\mathbf{y}\neq\mathbf{z}$ in the convex hull of $S$
which is not in the convex hull of $S^{\prime}$. As $\mathbf{y}$ is in the
convex hull of $S=S^{\prime}\cup\\{\mathbf{z}\\}$, there exist points
$\mathbf{s}_{1},\dots,\mathbf{s}_{k-1}\in S^{\prime}$ and nonnegative values
$\lambda_{1},\dots,\lambda_{k}$ summing to $1$ so that

$\mathbf{y}=\lambda_{1}\mathbf{s}_{1}+\dots+\lambda_{k-1}\mathbf{s}_{k-1}+\lambda_{k}\mathbf{z}.$

As $\mathbf{y}$ is not in the convex hull of $S^{\prime}$, $\lambda_{k}>0$. We
write $t=\lambda_{1}+\dots+\lambda_{k-1}$, and as $\mathbf{y}\neq\mathbf{z}$,
$0<t<1$. We write

$\mathbf{w}=\frac{\lambda_{1}}{t}\mathbf{s}_{1}+\dots+\frac{\lambda_{k-1}}{t}\mathbf{s}_{k-1}$

and observe that $\mathbf{w}$ is in the convex hull of $S^{\prime}$. We also
observe that $\mathbf{y}=t\mathbf{w}+(1-t)\mathbf{z}$. Hence,

$\mathbf{a}\boldsymbol{\cdot}\mathbf{y}=\mathbf{a}\boldsymbol{\cdot}(t\mathbf{w}+(1-t)\mathbf{z})=t\mathbf{a}\boldsymbol{\cdot}\mathbf{w}+(1-t)\mathbf{a}\boldsymbol{\cdot}\mathbf{z}<t\mathbf{a}\boldsymbol{\cdot}\mathbf{z}+(1-t)\mathbf{a}\boldsymbol{\cdot}\mathbf{z}=\mathbf{a}\boldsymbol{\cdot}\mathbf{z}.$

This completes the proof. ∎

Figure 4. A bidirectional connected difference DFA in $\mathbb{R}^{2}$ with no
loops drawn.

######  Theorem 4.3.

If $G=(V,E,\psi)$ is a bidirectional connected difference DFA in
$\mathbb{R}^{d}$, then $G$ is synchronizable.

###### Proof.

Let $G=(V,E,\psi)$ be a bidirectional connected difference DFA in
$\mathbb{R}^{d}$. By definition, $V\subset\mathbb{R}^{d}$. By Lemma 4.2 there
exists $\mathbf{z}\in V$ and a non-zero vector $\mathbf{a}$ such that

$\mathbf{a}\boldsymbol{\cdot}(\mathbf{z}-\mathbf{x})>0$

for all $\mathbf{x}\in V\setminus\\{\mathbf{z}\\}$.

We observe that if $P=(\mathbf{u},\dots,\mathbf{v})$ is a directed path in
$G$, then as $G$ is a difference DFA, $\psi(P)=\mathbf{v}-\mathbf{u}$. We let
$T$ be the set of all words $\sigma$ for which there exists a directed path
$P=(\mathbf{u},\dots,\mathbf{v})$ in $G$ such that $\psi(P)=\sigma$ and
$\mathbf{a}\boldsymbol{\cdot}(\mathbf{v}-\mathbf{u})<0$. Then, we let
$f:\Psi^{*}\rightarrow\\{-1,1\\}$ satisfy $f(\sigma)=-1$ if $\sigma\in T$ and
$f(\sigma)=1$ otherwise. We observe that for every directed path
$P=(\mathbf{u},\dots,\mathbf{v})$ in $G$ of length at least one,
$f(\psi(P))=1$ if and only if
$\mathbf{a}\boldsymbol{\cdot}(\mathbf{v}-\mathbf{u})\geq 0$. In particular,
every directed path $P=(\mathbf{u},\dots,\mathbf{z})$ of length at least one
is $f$-positive, and every directed path $P=(\mathbf{z},\dots,\mathbf{v})$ of
length at least one is $f$-negative.

By Theorem 3.1 it is sufficient to show there is an $f$-corner in $G$. We
claim $\mathbf{z}$ is an $f$-corner. For all $\mathbf{x}\neq\mathbf{z}$,
$\operatorname{dist}^{+}_{f}(\mathbf{x},\mathbf{z})=\operatorname{dist}(\mathbf{x},\mathbf{z})$,
as every path from $\mathbf{x}$ to $\mathbf{z}$ is $f$-positive and
$\operatorname{dist}^{+}_{f}(\mathbf{z},\mathbf{x})>\operatorname{dist}(\mathbf{z},\mathbf{x})$
as every path from $\mathbf{z}$ to $\mathbf{x}$ is $f$-negative.

As $G$ is bidirectional connected,
$\operatorname{dist}(\mathbf{x},\mathbf{z})=\operatorname{dist}(\mathbf{z},\mathbf{x})$,
so we conclude that

$\operatorname{dist}^{+}_{f}(\mathbf{x},\mathbf{z})=\operatorname{dist}(\mathbf{x},\mathbf{z})=\operatorname{dist}(\mathbf{z},\mathbf{x})<\operatorname{dist}^{+}_{f}(\mathbf{z},\mathbf{x})$

so
$\operatorname{dist}^{+}_{f}(\mathbf{x},\mathbf{z})<\operatorname{dist}^{+}_{f}(\mathbf{z},\mathbf{x})$
as desired. Given that $\mathbf{x}\neq\mathbf{z}$ was chosen without loss of
generality, we conclude that $\mathbf{z}$ is an $f$-corner. This completes the
proof. ∎

For an example of applying Theorem 4.3 to a fixed DFA, consider the difference
DFA $G$ in Figure 4. Let ${\mathbf{z}}=(0,0)$ (the bottommost and leftmost
vertex) and let ${\mathbf{a}}=(-1,-1)$. Then,
${\mathbf{a}}\cdot{\mathbf{z}}=0$, but for any ${\mathbf{x}}=(x,y)$ where
$x\geq 0$ and $y\geq 0$, ${\mathbf{a}}\cdot{\mathbf{x}}\geq 0$ if and only if
${\mathbf{x}}={\mathbf{z}}$. Hence, for each vertex $\mathbf{x}\in
V(G)\setminus\\{\mathbf{z}\\}$,
$\mathbf{a}\boldsymbol{\cdot}\mathbf{z}>\mathbf{a}\boldsymbol{\cdot}\mathbf{x}$.

With this example in mind, we observe that for a general difference DFA $G$,
whenever ${\mathbf{z}}$ is a point on the boundary of the convex hull of $V$
for which there exists hyperplane $H$ intersecting the convex hull of $V$
exactly at ${\mathbf{z}}$, we can define $f$ so that $\mathbf{z}$ is an
$f$-corner of $G$. For this, we let ${\mathbf{a}}$ be a vector orthogonal to
$H$ and pointing away from the closed affine-half space defined by $H$ and
containing $V$, and then we define $f$ as in Theorem 4.3. In this case, the
convex hull of $V$ is a polytope, and $\mathbf{z}$ is a vertex (or _corner_)
of this polytope. This idea motivates our name for the cornering strategy.

######  Lemma 4.4 ([6, Theorem.1]).

If $G=(V,E)$ is a simple graph of order $n$ and minimum degree $\delta\geq 2$,
then

$\operatorname{diam}(G)\leq\frac{3n}{\delta+1}-1$

We note that Lemma 4.4 has been improved in [12] to
$\operatorname{diam}(G)\leq\frac{3(n-t)}{\delta+1}-1+\frac{3}{\delta+1}$ for
$\delta,\operatorname{diam}(G)\geq 5$, where $t$ is the number of distinct
terms in the degree sequence of $G$. In some cases this might give a large
improvement over Lemma 4.4. However for general graphs, the classical result
of Erdős, Pach, Pollack, and Tuza [6] given in Lemma 4.4 is sufficient.

######  Theorem 4.5.

If $G=(V,E,\psi)$ is a bidirectional connected difference DFA in
$\mathbb{R}^{d}$ of order $n$ satisfying $|N^{+}(\mathbf{x})|\geq k\geq 2$ for
all $\mathbf{x}\in V$, then $G$ has a synchronizing word of length at most

$\frac{9n^{3}-9n^{2}}{2(k+1)^{2}}+\frac{3n-3n^{2}}{2(k+1)}$

Thus, if $n\geq 5$ and $k\geq 3\sqrt{\frac{n}{2}}-1$, then $G$ has a
synchronizing word of length strictly less than $(n-1)^{2}$.

###### Proof.

Let $G=(V,E,\psi)$ be a bidirectional connected difference DFA in
$\mathbb{R}^{d}$ of order $n$, and suppose that $|N^{+}(\mathbf{x})|\geq k\geq
2$ for all $\mathbf{x}\in V$. In the proof of Theorem 4.3, we showed that
there exists a function $f:\Psi^{*}\rightarrow\\{-1,1\\}$ and an $f$-corner
$\mathbf{z}\in V$ such that
$\operatorname{dist}(\mathbf{x},\mathbf{z})=\operatorname{dist}^{+}_{f}(\mathbf{x},\mathbf{z})$
for all $\mathbf{x}\in V$. Then, Theorem 3.1 implies that there is a
$\mathbf{z}$-synchronizing word of length at most $\frac{(n-1)D(D+1)}{2}$,
where $D=\max_{\mathbf{x}\in
V}\operatorname{dist}^{+}_{f}(\mathbf{x},\mathbf{z})\leq\operatorname{diam}(G)$,
and $\operatorname{diam}(G)$ is the directed diameter of $G$.

We note that as $G$ is a bidirectional connected DFA, the directed diameter of
$G$ is equal to the diameter of the underlying simple graph of $G$, which we
call $H$. Furthermore, we note that for all $\mathbf{x}\in V$,
$\deg_{H}(\mathbf{x})-1\leq|N^{+}_{G}(\mathbf{x})|\leq\deg_{H}(\mathbf{x})$.
Hence, $\delta(H)\geq k\geq 2$ for all $n\geq 5$. Then, Lemma 4.4 implies that

$\displaystyle
D\leq\operatorname{diam}(G)=\operatorname{diam}(H)\leq\frac{3n}{\delta(H)+1}-1\leq\frac{3n}{k+1}-1.$

Thus, $D(D+1)\leq\frac{9n^{2}}{(k+1)^{2}}-\frac{3n}{k+1}$ implying that

$\displaystyle\frac{(n-1)D(D+1)}{2}\leq\frac{9n^{3}-9n^{2}}{2(k+1)^{2}}+\frac{3n-3n^{2}}{2(k+1)},$

as desired. Letting $k\geq 3\sqrt{\frac{n}{2}}-1$, we note that
$\frac{3n}{k+1}-1\leq\sqrt{2n}-1$. Thus, for $n\geq 5$,

$D(D+1)\leq(2n-2\sqrt{2n}+1)+(\sqrt{2n}-1)=2n-\sqrt{2n}<2(n-1),$

which implies that $\frac{(n-1)D(D+1)}{2}<(n-1)^{2}$. This concludes the
proof. ∎

##  5\. Ordered DFAs

The goal of this section is to generalize a criterion from [1] for a DFA to be
synchronizable. The criterion from [1] involves the existence of a total
ordering of the vertices of a DFA which is preserved by the action of any word
in $\Psi^{*}$. In this section, we show that any DFA admitting a partial order
of the vertices with at least one universally comparable element satisfying a
weaker assumption is also synchronizable. The rest of the section explores the
consequences of this result, largely by considering for which $n$-element DFAs
our method implies a synchronizing word of length at most $(n-1)^{2}$.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$. For a function
$f:\Psi^{*}\rightarrow\\{-1,1\\}$ we say that $G$ is an _$f$ -partially
ordered DFA_ if the following properties are satisfied. First, for all $u,v\in
V$, there is an $f$-positive walk from $u$ to $v$. Second, there exists a
partial order $\mathcal{P}=(V,\preceq)$ such that

  1. (1)

for all $f$-positive words $\sigma\in\Psi^{*}$, $v\preceq w$ implies
$v(\sigma)\preceq w(\sigma)$, and

  2. (2)

there exists an element $z\in V$ such that for all $v\in V$, either $z\preceq
v$ or $v\preceq z$.

For an example of a partially ordered DFA, see Figure 5. In this example, $f$
is the function which maps all words to $1$. Notice that the DFA in Figure 5
is not a difference DFA.

Our proof employs the same approach as that of Theorem 4.3 but is somewhat
simpler, although not shorter. As such, we do not require the use of Theorem
3.1. Despite this, we note that the same principles underlying Theorem 3.1 are
applied here.

######  Theorem 5.1.

If $G=(V,E,\psi)$ is an $f$-partially ordered DFA of order $n$, then $G$ has a
synchronizing word of length at most $d(2n-2)$, where $d=\max_{u,v\in
V}\operatorname{dist}^{+}_{f}(u,v)$.

###### Proof.

Let $G=(V,E,\psi)$ be an $f$-partially ordered DFA of order $n$ whose partial
order is given by the binary relation $\preceq$. Let $m$ be a maximal element
of $(V,\preceq)$, and let $z\in V$ be a vertex such that for all $v\in V$,
either $z\preceq v$ or $v\preceq z$. Such a vertex $z$ exists by (2). Consider
$u,v\in V$ such that $u\prec v$. By our definition of an $f$-partially ordered
DFA, there exists an $f$-positive walk from $u$ to $m$. Hence, we let $\sigma$
be an $f$-positive word satisfying $u(\sigma)=m$. As $\sigma$ is $f$-positive,
it follows from (1) that $u(\sigma)=m\preceq v(\sigma)$. As $m$ is maximal,
this implies that $v(\sigma)=m=u(\sigma)$. For each $u\in V$, let $\sigma_{u}$
be a shortest $f$-positive word such that $u(\sigma_{u})=m$. Also, let $\tau$
be a shortest $f$-positive word such that $m(\tau)=z$.

Initialize a robot on each vertex of $G$, and let $R$ be the robot initialized
at $m$. We say a robot $r$ is _synchronized_ if it occupies the same element
as $R$. Note that by this definition, $R$ is synchronized at all points
throughout our process. We write $\pi_{0}$ for the empty word. For $i\geq 1$,
whenever we define a word $\pi_{i}$, we assume that the word $\pi_{i}$ is
passed to all robots.

We proceed in iterations. For $i\geq 1$, we carry out iteration $i$ as
follows. If all robots are synchronized, then halt. Otherwise, we assume that
the words $\pi_{0},\pi_{1},\dots,\pi_{i-1}$ have already been defined and
passed to our robots. We proceed in cases based on the positions of our
robots, as follows.

Case 1: If $R$ occupies $m$ and there exists a robot $r$ with current position
$u\prec m$, then:

Pass the word $\pi_{i}=\sigma_{u}$ to all robots. As
$u(\pi_{i})=m=m(\pi_{i})$, $r$ is synchronized after receiving $\pi_{i}$. As
$R$ had current state $m$ prior to $\pi_{i}$ being defined, and as
$m(\pi_{i})=m$, $R$ remains at $m$. Then, we proceed to iteration $i+1$, in
which the process halts or follows Case 1 or 2.

Case 2: If $R$ occupies $m$ and there exists no robot $r$ with current state
$u\prec m$, then:

Let $\pi_{i}=\tau$. As $R$ had current position $m$ prior to $\pi_{i}$ being
defined, $R$ now has current position $m(\pi_{i})=m(\tau)=z$. Then, we proceed
to iteration $i+1$, in which the process halts or follows Case 3.

Case 3: If $R$ occupies $z$, then:

There exists a robot $r$ with current position $u\neq z$. By assumption,
either $u\prec z$ or $z\prec u$. If $u\prec z$, then let $\pi_{i}=\sigma_{u}$;
otherwise $z\prec u$, and we let $\pi_{i}=\sigma_{z}$. In both cases,
$u(\pi_{i})=m=z(\pi_{i})$, implying that $r$ is synchronized and that $R$
occupies $m$. Then, we proceed to iteration $i+1$, in which our process halts
or follows Case 1 or 2.

Let $\pi_{k}$ be the last word defined by our procedure. We observe that for
each $i\in[0,k]$, after $\pi_{0},\dots,\pi_{i}$ are passed, at least
$1+\lceil\frac{i}{2}\rceil$ robots are synchronized. Indeed, each time we
follow Case 1 or 3, at least one unsynchronized robot becomes synchronized.
Furthermore, each time we follow Case 2 in some iteration $i$, the following
iteration $i+1$ follows Case 3. As the first iteration follows Case 1, it thus
follows that at least $1+\lceil\frac{i}{2}\rceil$ robots are synchronized
after iterations $1,\dots,i$. As all $n$ robots are synchronized after passing
$\pi_{1},\dots,\pi_{k}$, it follows that $k\leq 2(n-1)$. Thus,
$\pi_{1}\dots\pi_{k}$ is a synchronizing word, and as each $\pi_{i}$
corresponds to a shortest $f$-positive walk, $|\pi_{1}\dots\pi_{k}|\leq kd\leq
2d(n-1)=d(2n-2)$. This completes the proof. ∎

Figure 5. The DFA in the figure is an example of a partially ordered DFA whose
vertex set is a subset of $\mathbb{Z}^{2}$, equipped with the partial order
$(x_{1},y_{1})\preceq(x_{2},y_{2})$ if and only if $x_{1}\leq x_{2}$ and
$y_{1}\leq y_{2}$. Loops are not drawn in the figure.

Observe that if $\mathcal{P}$ or $f$ satisfies additional assumptions, then we
may improve the upper bound on the length of a shortest synchronizing word.
Both of the following corollaries demonstrate this fact for specific classes
of partially ordered DFAs.

Given a partially ordered set $\mathcal{P}=(X,\preceq)$ we say that an element
$z\in X$ is _maximum_ if $x\leq z$ for all $z\in X$.

######  Corollary 5.2.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$. If there exists a partial
order $\mathcal{P}=(V,\preceq)$ such that

  1. (1)

for all words $\sigma\in\Psi^{*}$, $v\preceq w$ implies $v(\sigma)\preceq
w(\sigma)$, and

  2. (2)

$\mathcal{P}$ has a maximum element $z\in V$,

then $G$ has a synchronizing word of length at most $(n-1)^{2}$.

###### Proof.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$ with a partial order
$\mathcal{P}=(V,\preceq)$ satisfying the assumptions of the corollary. Define
a function $f:\Psi^{*}\rightarrow\\{-1,1\\}$ that maps all words to $1$. We
observe that $G$ is $f$-partially ordered.

Now, we execute the algorithm in the proof of Theorem 5.1. As $z$ is maximum,
the algorithm halts before ever reaching Case 2. Therefore, each iteration of
the algorithm follows Case 1 or Case 3. Hence, the algorithm in the proof of
Theorem 5.1 produces a synchronizing word of length at most $d(n-1)$, where
$d=\operatorname{diam}(G)$. As $d\leq n-1$, $G$ has a synchronizing word of
length at most $(n-1)^{2}$, completing the proof. ∎

######  Corollary 5.3.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$. If there exists a total
order $\mathcal{P}=(V,\preceq)$ such that $v\preceq w$ implies
$v(\sigma)\preceq w(\sigma)$ for all words $\sigma\in\Psi^{*}$, then $G$ has a
synchronizing word of length at most $n-1$.

###### Proof.

Let $G=(V,E,\psi)$ be a connected DFA of order $n$, and suppose that there
exists a total order $\mathcal{P}=(V,\preceq)$ such that for all words
$\sigma\in\Psi^{*}$, $v\preceq w$ implies $v(\sigma)\preceq w(\sigma)$. Let
$u$ be the minimum element of $\mathcal{P}$ and $v$ the maximum element of
$\mathcal{P}$. Then, let $P$ be a shortest path from $u$ to $v$ in $G$. We
observe that for all $w\in V$, $v=u(\psi(P))\preceq w(\psi(P))$, implying that
$w(\psi(P))=v$. Thus, $\psi(P)$ is a $v$-synchronizing word. As $\psi(P)$ is a
shortest path, $|\psi(P)|\leq\operatorname{diam}(G)\leq n-1$. This concludes
the proof. ∎

In [1] Ananichev and Volkov consider the problem of synchronizing DFAs which
admit a total ordering $\mathcal{P}=(V,\preceq)$ such that for all words
$\sigma\in\Psi^{*}$, $v\preceq w$ implies $v(\sigma)\preceq w(\sigma)$. The
primary result of this paper (Theorem 1) proves that if $G$ is such a DFA and
$k\geq 1$ is an integer, then there exists a word $\sigma_{k}$ such that
$|\sigma_{k}|\leq n-k$ and $|\\{u(\sigma_{k}):u\in V\\}|\leq k$. Letting
$k=1$, $\sigma_{k}$ is a synchronizing word. Thus, Corollary 5.3 implies
Theorem 1 of [1] in the case where $k=1$. Hence, Theorem 5.1 is a
generalization of the work in [1].

Notably Theorem 1 from [1] was generalized in Theorem 1 from [2]. In the light
of this, it seems natural to ask whether Theorem 5.1 can be similarly
extended. Furthermore, it is natural to ask if our assumption that there
exists a vertex $z\in V$ such that for all $v\in V$, $v\preceq z$ or $z\preceq
v$ is indeed required. That is, does there exist a DFA $G$ admitting a non-
trivial partial order $\mathcal{P}$ with no universally comparable element,
where $\mathcal{P}$ is preserved by the action of every word, but $G$ is not
synchronizable?

The answer, at least to the second question, is yes. For example, consider the
following DFA $G$ with vertex set $V=\mathbb{Z}_{n}\times\mathbb{Z}_{2}$. We
let $G$ have an associated alphabet
$\Psi=\\{\texttt{up},\texttt{down},\texttt{turn}\\}$. We describe the edge set
$E$ of $G$ and the labelling function $\psi:E\rightarrow\Psi$ by defining
$v(\sigma)$ for each $v\in V$ and $\sigma\in\Psi$. For each
$k\in\mathbb{Z}_{n}$, we let $(k,0)(\texttt{up})=(k,1)(\texttt{up})=(k,1)$,
and we let $(k,0)(\texttt{down})=(k,1)(\texttt{down})=(k,0)$. Furthermore, for
each $(k,i)\in V$, we let $(k,i)(\texttt{turn})=(k+1,i)$. We also define a
partial order $\mathcal{P}=(V,\preceq)$ so that reflexivity holds,
$(k,0)\preceq(k,1)$ for all $k\in\mathbb{Z}_{n}$, and so that every other pair
of elements in $V$ is incomparable.

We observe that $G$ admits a non-trivial partial order $\mathcal{P}$ with no
universally comparable element, where $\mathcal{P}$ is preserved by the action
of every word. However, $G$ is not synchronizable, as for all distinct
$k,t\in\mathbb{Z}_{n}$ and all words
$\sigma\in\\{\texttt{up},\texttt{down},\texttt{turn}\\}^{*}$,
$(k,i)(\sigma)=(k+x,i^{\prime})\neq(t+x,i^{\prime})=(t,i)(\sigma)$, where
$i^{\prime}\in\mathbb{Z}_{n}$ and $x$ is the number of times turn appears in
$\sigma$.

##  6\. Synchronizing Disjoint DFAs

In this section we consider the problem of synchronizing a DFA $G$ to a
prescribed state $u$ and a second DFA $H$ to a prescribed state $v$ using a
common word $\sigma$. We do not assume that $G$ and $H$ are related beyond
having the same alphabet $\Psi$. This is a natural problem to consider for
some applications. For example, if we take $G=(V_{1},E_{1},\psi_{1},x)$ and
$H=(V_{2},E_{2},\psi_{2},y)$ to be distinct difference DFAs in
$\mathbb{R}^{2}$ and let $u=v$, then this setting models the problem of having
two delivery robots receiving the same commands moving through different parts
of a warehouse so that at some time $t$, we require both robots to arrive at
the front door to drop off their respective packages. Here, we assume that
both robots receive the same commands. This is reasonable when dealing with
groups of simple machines given that distinguishing different types of
commands might be beyond the capabilities of such machines.

To this end, given DFAs $G$ and $H$, we define the DFA $G+H=(V,E,\psi,(x,y))$
as the disjoint sum of $G$ and $H$, as follows:

  1. (1)

$V=V_{1}\times V_{2}$, and

  2. (2)

$((a,b),(u,v))\in E$ if and only if $(a,u)\in E_{1}$, and $(b,v)\in E_{2}$,
and $\psi_{1}(a,u)=\psi_{2}(b,v)$, and

  3. (3)

$\psi((a,b),(u,v))=\psi_{1}(a,u)=\psi_{2}(b,v)$ for all $((a,b),(u,v))\in E$.

We note that the current state of $G+H$ captures the current states of $G$ and
$H$. In particular, for all $u\in V_{1}$, $v\in V_{2}$, and
$\sigma\in\Psi^{*}$, $(u,v)(\sigma)=(u(\sigma),v(\sigma))$.

For an example about how this operation is of natural interest, suppose that
we have a difference DFA $G$ that models a location of a simple machine and a
DFA $H$ which models the current state of the same machine. As the machine is
simple, suppose that the commands it receives to change location and state are
the same. Constructing such machines may be cheaper, or in some contexts such
as for microscopic machines, necessary. As the controller, we are interested
in the state and location of the machine. Thus, the DFA $G+H$ is required, as
we want the machine to be in the correct location with the correct state to
accomplish its task.

The question now is, for which $u\in V_{1}$ and $v\in V_{2}$ does there exist
a synchronizing word which results in a current state of $(u,v)$ in $G+H$? We
note that if $G+H$ is connected and synchronizable, then any current state of
$G+H$ is achievable by a synchronizing word. That is to reach the desired
current state $a$, simply apply a synchronizing word $\sigma$ to reach some
state $b$, then apply a word $\tau$ for which $b(\tau)=a$. However, even if
$G$ and $H$ are connected, it may not hold that $G+H$ is connected. See Figure
6 for an example of how the disjoint sum of two connected DFAs $G$ and $H$ can
be disconnected. Hence, such a word $\tau$ need not exist for every $(u,v)\in
V$. Hence, it is worth asking for which states $(u,v)$ in $G+H$ there exists a
$(u,v)$-synchronizing word.

$v$$u$$G:$$z$$y$$x$$H:$$G+H:$

Figure 6. An example of disjoint sum of DFAs with no loops drawn. In the
drawing of $G+H$, the three vertices on the left have the form $(u,\cdot)$
while the three vertices on the right have the form $(v,\cdot)$.

We are able to prove that if DFAs $G$ and $H$ have $f$-corners $u$ and $v$,
respectively, then $G+H$ is $(u,v)$-synchronizable. It is unclear if $(u,v)$
is always an $f$-corner in $G+H$. Thus, our proof employs a slightly more
complicated approach than the cornering strategy; however the fundamentals of
the proof are the same.

######  Theorem 6.1.

Let $G=(V_{1},E_{1},\psi_{1})$ and $H=(V_{2},E_{2},\psi_{2})$ be DFAs over the
same alphabet $\Psi$. If $f:\Psi^{*}\rightarrow\\{-1,1\\}$ and $G$ and $H$
have $f$-corners $u$ and $v$, respectively, then $G+H$ is
$(u,v)$-synchronizable.

###### Proof.

Let $G=(V_{1},E_{1},\psi_{1})$ and $H=(V_{2},E_{2},\psi_{2})$ be DFAs over the
same alphabet $\Psi$ such that for some function
$f:\Psi^{*}\rightarrow\\{-1,1\\}$, $G$ and $H$ have $f$-corners $u$ and $v$,
respectively. We note that by Theorem 3.1, $G$ is $u$-synchronizable and $H$
is $v$-synchronizable.

Let $\sigma$ be a $u$-synchronizing word for $G$, and let $\tau$ be a
$v$-synchronizing word for $H$. Then, for any two vertices $(x_{1},y_{1})$ and
$(x_{2},y_{2})$ in $G+H$, we have
$(x_{1},y_{1})(\sigma\tau)=(x_{2},y_{2})(\sigma\tau)=(z,v)$, where
$z=u(\tau)$. It remains to show that there exists a directed walk in $G+H$
from $(z,v)$ to $(u,v)$. To this end, we imagine that a robot $r$ occupies
$(z,v)$, and we aim to construct a word $\sigma$ that moves $r$ to $(u,v)$.

To construct our word $\sigma,$ we iterate
$i=0,1,\dots,\operatorname{dist}_{G,f}^{+}(z,u)$. We write
$(x_{0},y_{0})=(z,v)$, and we write $(x_{i},y_{i})$ for the position of $r$ at
the end of each iteration $i$. For each $i$, we let
$D_{i}=\operatorname{dist}^{+}_{G,f}(x_{i},u)+\operatorname{dist}^{+}_{H,f}(y_{i},v)$.
We note that $D_{0}=\operatorname{dist}_{G,f}^{+}(z,u)$. Note that if
$D_{i}=0$, then $r$ occupies $(u,v)$ at the end of iteration $i$.

At the beginning of each iteration $i$, the robot $r$ has current position
$(x_{i-1},y_{i-1})$. For $i\geq 1$, if $i$ is odd, let $W_{i}$ be a shortest
$f$-positive walk in $G$ from $x_{i-1}$ to $u$, and if $i$ is even, let
$W_{i}$ be a shortest $f$-positive walk in $H$ from $y_{i-1}$ to $v$. Let
$\sigma_{i}=\psi(W_{i})$, and pass $\sigma_{i}$ to $r$; then,
$x_{i}=x_{i-1}(\sigma_{i})$ and $y_{i}=y_{i-1}(\sigma_{i})$. This completes
iteration $i$.

Observe that if $i$ is odd then $x_{i}=u$, and if $i$ is even then $y_{i}=v$.
So, if $i\geq 1$ is odd, then

$D_{i}=\operatorname{dist}_{H,f}^{+}(y_{i},v)<\operatorname{dist}_{H,f}^{+}(v,y_{i})\leq|\sigma_{i}|=D_{i-1},$

as $v$ is an $f$-corner and $y_{i}=y_{i-1}(\sigma_{i})=v(\sigma_{i})$ for an
$f$-positive word $\sigma_{i}$. Similarly if $i\geq 1$ is even, then

$D_{i}=\operatorname{dist}_{G,f}^{+}(x_{i},u)<\operatorname{dist}_{G,f}^{+}(u,x_{i})\leq|\sigma_{i}|=D_{i-1},$

as $u$ is an $f$-corner and $x_{i}=x_{i-1}(\sigma_{i})=u(\sigma_{i})$ for an
$f$-positive word $\sigma_{i}$.

Thus, for all $1\leq i\leq\operatorname{dist}^{+}_{G,f}(z,u)$,
$D_{i}<D_{i-1}$, implying that when $k=\operatorname{dist}^{+}_{G,f}(z,u)$,
$D_{k}=0$. Hence, there exists a directed walk $W$ from $(z,v)$ to $(u,v)$ in
$G+H$ such that
$\psi(W)=\sigma_{1}\dots\sigma_{k}=\psi(W_{1})\psi(W_{2})\dots\psi(W_{k})$.
Therefore, $\sigma\tau\psi(W)$ is a $(u,v)$-synchronizing word. This completes
the proof. ∎

##  7\. Future Work

While we have resolved several questions regarding the synchronizablility of
DFAs, many more questions remain open. Of course, chief among these is Černý’s
conjecture; however we will focus our attention here on more manageable, or at
least more novel open problems.

The first of these problems is whether or not the bound given in Theorem 3.1
for the length of a shortest synchronizing word is tight? That is, do there
exist DFAs whose shortest synchronizing words have length approximately
$\frac{(n-1)d(d+1)}{2}$ where $d=\max_{u\in
V}\operatorname{dist}_{f}^{+}(z,u)$ for an $f$-corner $z$? Moreover, if the
answer is yes, then does this remain true if we force $d\geq N$ for some large
integer $N$?

######  Conjecture 7.1.

Let $\Psi$ be an alphabet, $f:\Psi^{*}\rightarrow\\{-1,1\\}$, and
$d\in\mathbb{N}$. There exists a constant $c$ independent of $d$, and DFA
$G=(V,E,\psi)$ of some order $n$ such that $G$ has an $f$-corner $x$, where
$d=\max_{u\in V}\operatorname{dist}^{+}_{f}(u,x)$ and each synchronizing word
for $G$ has length at least $cnd^{2}$.

From here, we ask how far can our results for difference DFAs be expanded and
generalized. The first natural conjecture here is that the assumption of
connected bidirectionality made in Theorem 4.3 can be relaxed to connectivity.

######  Conjecture 7.2.

If $G=(V,E,\psi)$ is a connected difference DFA in $\mathbb{R}^{d}$, then $G$
is synchronizable.

Alternatively we can ask if the assumption of each vertex having a large out-
neighbourhood in Theorem 4.5 is required.

######  Conjecture 7.3.

If $G=(V,E,\psi)$ is a difference DFA in $\mathbb{R}^{d}$ on $n$ vertices,
then $G$ has a synchronizing sequence of length at most $(n-1)^{2}$.

Finally, as with any good question involving the real numbers, we ask if our
results hold in more general groups.

######  Question 7.4.

For which groups $X$ can every connected or bidirectional connected difference
DFA in $X$ be synchronized?

To conclude, we ask questions regarding the disjoint sum of two or more DFAs.
Out of all of the questions we give here, this question seems most applicable,
especially as one of our primary motivations for considering the disjoint sum
is simple machines, which in modern contexts are often deployed at scale.

######  Conjecture 7.5.

Let $k\geq 3$, $\Psi$ be an alphabet, and $f:\Psi^{*}\rightarrow\\{-1,1\\}$.
If $G_{1},\dots,G_{k}$ are distinct DFAs over $\Psi$ and for all $i\in[k]$
there exists an $f$-corner $x_{i}$ in $G_{i}$, then $G=G_{1}+\dots+G_{k}$ is
$(x_{1},\dots,x_{k})$-synchronizable.

######  Question 7.6.

For which DFAs $G$ and $H$ over the same alphabet is $G+H$
$(u,v)$-synchronizable for all $u\in V(G)$ and $v\in V(H)$?

## References

  * [1] Dimitry S Ananichev and Mikhail V Volkov.  Synchronizing monotonic automata.  Theoretical Computer Science, 327(3):225–239, 2004.
  * [2] Dimitry S Ananichev and Mikhail V Volkov.  Synchronizing generalized monotonic automata.  Theoretical Computer Science, 330(1):3–13, 2005.
  * [3] Ján Černỳ.  Poznámka k homogénnym experimentom s konečnỳmi automatmi.  Matematicko-fyzikálny časopis, 14(3):208–216, 1964.
  * [4] Louis Dubuc.  Sur les automates circulaires et la conjecture de černỳ.  RAIRO-Theoretical Informatics and Applications, 32(1-3):21–34, 1998\.
  * [5] David Eppstein.  Reset sequences for monotonic automata.  SIAM Journal on Computing, 19(3):500–510, 1990.
  * [6] Paul Erdős, János Pach, Richard Pollack, and Zsolt Tuza.  Radius, diameter, and minimum degree.  Journal of Combinatorial Theory, Series B, 47(1):73–79, 1989.
  * [7] Peter Frankl.  An extremal problem for two families of sets.  European Journal of Combinatorics, 3(2):125–127, 1982.
  * [8] Jarkko Kari.  Synchronizing finite automata on Eulerian digraphs.  Theoretical Computer Science, 295(1-3):223–232, 2003.
  * [9] AE Laemmel.  A general class of discrete codes and certai of their properties.  Res. rep, 1956.
  * [10] Arthur E Laemmel and Beulah Rudner.  Study on application of coding theory.  Polytechnic Inst. of Brooklyn, 1963.
  * [11] Chung Laung Liu.  Some memory aspects of finite automata.  PhD thesis, Massachusetts Institute of Technology, Department of Electrical Engineering, 1962.
  * [12] Simon Mukwembi.  A note on diameter and the degree sequence of a graph.  Applied mathematics letters, 25(2):175–178, 2012.
  * [13] Anthony L. Peressini, Francis E. Sullivan, and J. J. Uhl, Jr.  The mathematics of nonlinear programming.  Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1988.
  * [14] Jean-Eric Pin.  On two combinatorial problems arising from automata theory.  In North-Holland Mathematics Studies, volume 75, pages 535–548. Elsevier, 1983.
  * [15] Yaroslav Shitov.  An improvement to a recent upper bound for synchronizing words of finite automata.  arXiv preprint arXiv:1901.06542, 2019.
  * [16] Marek Szykuła.  Improving the upper bound on the length of the shortest reset words.  arXiv preprint arXiv:1702.05455, 2017.
  * [17] Avraham N Trahtman.  Modifying the upper bound on the length of minimal synchronizing word.  In Fundamentals of Computation Theory: 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Proceedings 18, pages 173–180. Springer, 2011.
  * [18] Mikhail Vladimirovich Volkov.  Synchronization of finite automata.  Uspekhi Matematicheskikh Nauk, 77(5):53–130, 2022.