Affiliations: [a] Institute of Natural Sciences and Mathematics, Ural Federal University, Ekaterinburg, Russia, [email protected] | [b] Dipartimento di Matematica, Politecnico di Milano, Milano, Italy, [email protected]
Correspondence:
[*]
Address for correspondence: Institute of Natural Sciences and Mathematics, Ural Federal University, Lenina St. 51, 620000 Ekaterinburg, Russia
Note: [†] The author acknowledges support from the Russian Foundation for Basic Research, grant no. 16-01-00795, the Ministry of Education and Science of the Russian Federation, project no. 1.3253.2017, and the Competitiveness Enhancement Program of Ural Federal University.
Abstract: We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We prove that for every ideal language there exists a strongly connected synchronizing automaton from some special class for which given language serves as the language of reset words. This class is formed by trim automata recognizing left quotients of principal left ideal languages. We show that the minimal automaton recognizing a left quotient of a principal left ideal can be viewed as a synchronizing automaton for which given finitely generated ideal serves as the language of reset words.
Keywords: ideal language, synchronizing automaton, reset word, reset complexity, reset left regular decomposition, strongly connected automaton
