Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)
Consider the two functions: $g_{\sa{a}}(i)=(i+1) \bmod n$,
$g_{\sa{b}}(i) = \min\{i,g_{\sa{a}}(i)\}$. For $n=3$ they are illustrated by
the automaton.
As shown on the table below the word $w=\sa{baab}$ is synchronising since the
image of the set $\{0,1,2\}$ by $g_w$ is the singleton $\{0\}$.
The word obviously synchronises every pair but the table shows additional
synchonisers like $\sa{b}$ for the pair $(0,2)$, $\sa{baa}$ for the pair
$(0,1)$ and $\sa{ba}$ for the pair $(1,2)$.
| $w$ | | | $\sa{b}$ | | $\sa{a}$ | | $\sa{a}$ | | $\sa{b}$ | |
| $g_w(0)$ | = | 0 | $\leftarrow$ | 2 | $\leftarrow$ | 1 | $\leftarrow$ | 0 | $\leftarrow$ | 0 |
| $g_w(1)$ | = | 0 | $\leftarrow$ | 0 | $\leftarrow$ | 2 | $\leftarrow$ | 1 | $\leftarrow$ | 1 |
| $g_w(2)$ | = | 0 | $\leftarrow$ | 2 | $\leftarrow$ | 1 | $\leftarrow$ | 0 | $\leftarrow$ | 2 |
|
Problem 123: Synchronising Words
|
|
The problem deals with the synchronisation of the composition of functions
from $I_n=\{0,1,\dots,n-1\}$ to itself for a positive integer $n$.
For two such functions $f_{\sa{a}}$ and $f_{\sa{b}}$, a word
$w\in\{\sa{a},\sa{b}\}^+$ encodes their composition $f_w = h_0\circ
h_1\circ\cdots\circ h_{|w|-1}$ when $h_i=f_{\sa{a}}$ if $w[i]=\sa{a}$ and
$h_i=f_{\sa{b}}$ if $w[i]=\sa{b}$.
(Note functions $h_i$ are applied to elements of $I_n$ in decreasing order
of $i$ as usual, i.e. from right to left according to $w$.)
The word $w$ is said to be {\it synchronising} if the
set $f_w(I_n)$ contains a single element.
A useful notion is that of a pair synchroniser: a word
$u\in\{\sa{a},\sa{b}\}^*$ is a synchroniser of the pair $(i,j)$, $i,j\in
I_n$, if $f_u(i)=f_u(j)$.
For any positive integer $n$ the word $w=\sa{b}(\sa{a}^{n-1}\sa{b})^{n-2}$ is
a synchronising word of the functions $g_{\sa{a}}$ and $g_{\sa{b}}$.
It is more difficult to see that it is a shortest such word in this particular
case.
This yields a quadratic lower bound on the length of a synchronising words.
Show that a pair of functions admits a synchronising word if and only if
there exists a synchroniser for each pair $(i,j)$ of elements of $I_n$.
Compute a synchronising word from synchronisers.
Show how to check in quadratic time if a pair of functions admits a
synchronising word.
Check pair synchronisers.
References
M. Béal and D. Perrin. Synchronised automata. In V. Berthé and
M. Rigo, editors, Combinatorics, Words and Symbolic Dynamics, Encyclopedia
of Mathematics and its Applications, pages 213-240. Cambridge
University Press, 2016.
M. Szykula. Improving the upper bound on the length of the shortest
reset word. In R. Niedermeier and B. Vallée, editors, 35th Symposium
on Theoretical Aspects of Computer Science, STACS 2018, February 28
to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 56:1-56:13.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
