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

Abstract : Č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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620310
Contributor : Marie-Pierre Béal <>
Submitted on : Friday, September 30, 2016 - 9:49:02 AM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Saturday, December 31, 2016 - 1:02:29 PM

File

cerny.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

226

Files downloads

176