A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA

DOI10.1142/S0129054111008039zbMath1217.68121MaRDI QIDQ3086238

Dominique Perrin, Mikhail V. Berlinkov, Marie-Pierre Béal

Publication date: 30 March 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

Huffman codeČerný's conjecturesynchronized automatonsynchronized maximal prefix code

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45)

Related Items (28)

Strongly connected synchronizing automata and the language of minimal reset words ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ ON A CONJECTURE BY CARPI AND D'ALESSANDRO ⋮ Synchronizing Automata of Bounded Rank ⋮ Synchronizing Automata with Extremal Properties ⋮ An algorithm for road coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ Circular automata synchronize with high probability ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA ⋮ On incomplete and synchronizing finite sets ⋮ Finding DFAs with Maximal Shortest Synchronizing Word Length ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Algebraic synchronization criterion and computing reset words ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ Simplicity of augmentation submodules for transformation monoids ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Random walk in a finite directed graph subject to a road coloring ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Semicomputable points in Euclidean spaces ⋮ Experiments with Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• The road coloring problem
• Strongly transitive automata and the Černý conjecture
• Almost all complete binary prefix codes have a self-synchronizing string
• On synchronizing prefix codes

This page was built for publication: A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA