On the length of shortest 2-collapsing words

Abstract : Given a word w over a finite alphabet Sigma and a finite deterministic automaton A = < Q,Sigma,delta >, the inequality vertical bar delta(Q,w)vertical bar <= vertical bar Q vertical bar - k means that under the natural action of the word w the image of the state set Q is reduced by at least k states. The word w is k-collapsing (k-synchronizing) if this inequality holds for any deterministic finite automaton ( with k + 1 states) that satisfies such an inequality for at least one word. We prove that for each alphabet Sigma there is a 2-collapsing word whose length is vertical bar Sigma vertical bar(3)+6 vertical bar Sigma vertical bar(2)+5 vertical bar Sigma vertical bar/2. Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 letters.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.33--44
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00988185
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 16:15:26
Dernière modification le : mercredi 29 novembre 2017 - 10:26:21
Document(s) archivé(s) le : jeudi 7 août 2014 - 11:35:22

Fichier

983-4060-3-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00988185, version 1

Collections

Citation

Alessandra Cherubini, Andrzej Kisielewicz, Brunetto Piochi. On the length of shortest 2-collapsing words. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.33--44. 〈hal-00988185〉

Partager

Métriques

Consultations de la notice

374

Téléchargements de fichiers

228