CLR cover
Previous problem

Problem 123: Synchronising Words

Next problem

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.