Missing Factors of Ideals and Synchronizing Automata
Achille Frigeri, Emanuele Rodaro · Virtual Community of Pathological Anatomy (University of Castilla La Mancha) · 2019
Recently, a series of papers have started to look at \v{C}ern\'y's conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then \v{C}ern\'y's conjecture holds.