Generating Synchronizing Automata with Large Reset Lengths

2014/04/12 by Andrzej Kisielewicz, Kisielewicz, Andrzej, Marek Szykuła +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1404.3311

openalex publication_date 2014/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study synchronizing automata with the shortest reset words of relatively large length. First, we refine the Frankl-Pin result on the length of the shortest words of rank m, and the Béal, Berlinkov, Perrin, and Steinberg results on the length of the shortest reset words in one-cluster automata. The obtained results are useful in computation aimed in extending the class of small automata for which the Černý conjecture is verified and discovering new automata with special properties regarding synchronization.

Related

• Strong inapproximability of the shortest reset word
• The Černý conjecture for small automata: experimental report
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• Experimental Study of the Shortest Reset Word of Random Automata
• Algebraic synchronization criterion and computing reset words