Counting symbol switches in synchronizing automata

Henk Don, Hans Zantema

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

Instead of looking at the lengths of synchronizing words as in Cerný‘s conjecture, we look at the switch count of such words, that is, we only count the switches from one letter to another. Where the synchronizing words of the Cerný automata Cn have switch count linear in n, we wonder whether synchronizing automata exist for which every synchronizing word has quadratic switch count. The answer is positive: we prove that switch count has the same complexity as synchronizing word length. We give some series of synchronizing automata yielding quadratic switch count, the best one reaching 2/3n2 + O(n) as switch count. We investigate all binary automata on at most 9 states and determine the maximal possible switch count. For all 3 ≤ n ≤ 9, a strictly higher switch count can be reached by allowing more symbols. This behaviour differs from length, where for every n, no automata are known with higher synchronization length than Cn, which has only two symbols. It is not clear if this pattern extends to larger n. For n ≥ 12, our best construction only has two symbols.

Original languageEnglish
Pages (from-to)253-286
Number of pages34
JournalJournal of Automata, Languages and Combinatorics
Volume24
Issue number2-4
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • Cerný conjecture
  • Switch count
  • Synchronization

Fingerprint

Dive into the research topics of 'Counting symbol switches in synchronizing automata'. Together they form a unique fingerprint.

Cite this