A quadratic upper bound on the size of a synchronizing word in one-cluster automata - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

A quadratic upper bound on the size of a synchronizing word in one-cluster automata

Marie-Pierre Béal
  • Fonction : Auteur
  • PersonId : 841350
Dominique Perrin

Résumé

Černý’s conjecture asserts the existence of a synchronizing word of length at most (n-1)² for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state deterministic automaton satisfying the following additional property: there is a letter a such that for any pair of states p, q, one has p·a^r=q·a^s for some integers r, s (for a state p and a word w, we denote by p·w the state reached from p by the path labeled w). As a consequence, we show that for any finite synchronized prefix code with an n-state decoder, there is a synchronizing word of length O(n²). This applies in particular to Huffman codes.
Fichier principal
Vignette du fichier
cerny.pdf (153.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00620310 , version 1 (30-09-2016)

Identifiants

Citer

Marie-Pierre Béal, Dominique Perrin. A quadratic upper bound on the size of a synchronizing word in one-cluster automata. 13th International Conference on Developments in Language Theory (DLT 2009), Jun 2009, Stuttgart, Germany. pp.81-90, ⟨10.1007/978-3-642-02737-6_6⟩. ⟨hal-00620310⟩
112 Consultations
152 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More