%0 Journal Article
%T Some Aspects of Synchronization of DFA
%A Avraham Trahtman
%A <br>Avraham
%A Trahtman
%J 计算机科学技术学报
%D 2008
%I 
%X A word w is called synchronizing (recurrent, reset, directable) word of deterministic finite automata (DFA) if w brings all states of the automaton to a unique state. According to the famous conjecture of  erny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most (n–1)2. The problem is still open. It will be proved that the  erny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state (n > 2) synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than (n–1)2/2. The last important class of DFA involved and studied by Sch tzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See .
%K deterministic finite automata (DFA)
%K synchronization
%K aperiodic semigroup
%K 
%K erny conjecture<br>
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=495036FAC6918F50D0DDDA84C8D80E0D&yid=67289AFF6305E306&vid=EA389574707BDED3&iid=94C357A881DFC066&sid=4D0B71A09FA5A2A5&eid=0EE24608F5763811&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=1