Finding Short Synchronizing Words for Prefix Codes: Unless P = NP, the Shortest Synchronizing Word of a Binary Huffman Decoder Cannot Be Approximated Within c log nResearch Paper
A prefix code is a set of binary words none of which is a prefix of another; Huffman codes are the standard example. Such a code is decoded by an automaton that walks down the code tree and returns to the root after each codeword. A transmission error can make the decoder lose track of codeword boundaries. A synchronizing word brings the decoder to one…