Shortest synchronizing strings for Huffman codes

DOI10.1016/j.tcs.2009.06.005zbMath1171.94003OpenAlexW1993592647MaRDI QIDQ837184

Wojciech Plandowski, Marek Tomasz Biskup

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.06.005

zbMATH Keywords

finite automatonHuffman codeČerný conjecturesynchronizing string

Mathematics Subject Classification ID

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

Related Items (9)

Unnamed Item ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Synchronizing automata with coinciding cycles ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Algebraic synchronization criterion and computing reset words ⋮ An Extremal Series of Eulerian Synchronizing Automata

Cites Work

• Unnamed Item
• Synchronizing automata with a letter of deficiency 2
• Synchronizing codewords of \(q\)-ary Huffman codes
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Self-synchronizing Huffman codes (Corresp.)
• Reset Sequences for Monotonic Automata
• Almost all complete binary prefix codes have a self-synchronizing string
• On two Combinatorial Problems Arising from Automata Theory
• On the characterization of statistically synchronizable variable-length codes
• On the construction of statistically synchronizable codes
• On synchronizing prefix codes
• Construction of minimum-redundance codes with an optimum synchronizing property
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

This page was built for publication: Shortest synchronizing strings for Huffman codes