Skip to Main content Skip to Navigation
Journal articles

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*ar = q*as 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 :
Journal articles
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619778
Contributor : Marie-Pierre Béal <>
Submitted on : Sunday, February 24, 2013 - 9:02:47 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Saturday, May 25, 2013 - 2:40:08 AM

File

cernyJournalFinal.pdf
Files produced by the author(s)

Identifiers

Citation

Marie-Pierre Béal, Mikhail V. Berlinkov, Dominique Perrin. A quadratic upper bound on the size of a synchronizing word in one-cluster automata. International Journal of Foundations of Computer Science, World Scientific Publishing, 2011, 22 (2), pp.277-288. ⟨10.1142/S0129054111008039⟩. ⟨hal-00619778⟩

Share

Metrics

Record views

356

Files downloads

484