The Černý conjecture for aperiodic automata

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.3--10
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966534
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 17:01:53
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : jeudi 26 juin 2014 - 12:00:43

Fichier

649-2221-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966534, version 1

Collections

Citation

Avraham N. Trahtman. The Černý conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.3--10. 〈hal-00966534〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

215