Counting symbol switching in synchronizing automata

DOI10.25596/JALC-2019-253MaRDI QIDQ5208372zbMATH OpenOpenAlexFDO

Authors Henk Don, Hans Zantema

Publication date 15 January 2020

Full work available at URL https://arxiv.org/abs/1812.04050

zbMATH Keywords

switch countsynchronizationČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Instead of looking at the lengths of synchronizing words as in v{C}ern'y'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 v{C}ern'y automata $mathcal{C}_n$ 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 $frac23n^2+O(n)$ as switch count. We investigate all binary automata on at most 9 states and determine the maximal possible switch count. For all $3leqnleq9$, 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 $mathcal{C}_n$, which has only two symbols. It is not clear if this pattern extends to larger $n$. For $ngeq12$, our best construction only has two symbols.

Recommendations

• Slowly synchronizing automata with fixed alphabet size
• Experiments with Synchronizing Automata
• Experiments on Synchronizing Automata
• Synchronizing times for k-sets in automata
• scientific article; zbMATH DE number 6861928

This page was built for publication: Counting symbol switching in synchronizing automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5208372)