The Cerný conjecture for automata respecting intervals of a directed graph

Abstract : The Cerný's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n - 1)2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.61--72
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00966381
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 15:16:27
Dernière modification le : jeudi 7 septembre 2017 - 01:03:37
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:32:04

Fichier

2198-8396-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966381, version 1

Collections

Citation

Mariusz Grech, Andrzej Kisielewicz. The Cerný conjecture for automata respecting intervals of a directed graph. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.61--72. 〈hal-00966381〉

Partager

Métriques

Consultations de la notice

255

Téléchargements de fichiers

297