{"docId":395,"paperId":395,"url":"https:\/\/dmtcs.episciences.org\/395","doi":"10.46298\/dmtcs.395","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":82,"name":"Vol. 9 no. 2"}],"section":[],"repositoryName":"Hal","repositoryIdentifier":"hal-00966534","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00966534v1","dateSubmitted":"2015-03-26 16:19:25","dateAccepted":"2015-06-09 14:46:31","datePublished":"2007-01-01 08:00:00","titles":{"en":"The \\v Cern\u00fd conjecture for aperiodic automata"},"authors":["Trahtman, A. N."],"abstracts":{"en":"A word w is called a synchronizing (recurrent, reset, directable) word of a deterministic finite automaton (DFA) if w brings all states of the automaton to some specific state; a DFA that has a synchronizing word is said to be synchronizable. Cerny conjectured in 1964 that every n-state synchronizable DFA possesses a synchronizing word of length at most (n-1)2. We consider automata with aperiodic transition monoid (such automata are called aperiodic). We show that every synchronizable n-state aperiodic DFA has a synchronizing word of length at most n(n-1)\/2. Thus, for aperiodic automata as well as for automata accepting only star-free languages, the Cerny conjecture holds true."},"keywords":["[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}