Representation of (Left) Ideal Regular Languages by Synchronizing Automata

摘要

We follow language theoretic approach to synchronizing automata and Cerny's conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexity of a principal ideal language. Also we show a strict connection between principal left ideals and synchronizing automata. Actually, it is proved that all strongly connected synchronizing automata are homomorphic images of automata recognizing languages which are left quotients of principal left ideal languages. This result gives a restatement of Cerny's conjecture in terms of length of the shortest reset words of special quotients of automata in this class. Also in the present paper we characterize regular languages whose minimal deterministic finite automaton is synchronizing and possesses a reset word belonging to the recognized language. This characterization shows a connection with the notion of constant of a language introduced by Schuetzenberger.