Synchronizing random automata

Abstract : Conjecture that any synchronizing automaton with n states has a reset word of length (n - 1)(2) was made by. Cerny in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. In this paper we study a random automaton that is sampled uniformly at random from the set of all automata with n states and m(n) letters. We show that for m(n) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n(beta), beta > 1/2 we also show that any random automaton with high probability satisfies the. Cerny conjecture.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.95-108
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990454
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:29
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:06:15

Fichier

1456-5764-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990454, version 1

Collections

Citation

Evgeny Skvortsov, Yulia Zaks. Synchronizing random automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.95-108. 〈hal-00990454〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

324