Complexity and sliding-block decodability

A constrained system, or sofic system, S is the set of symbol strings generated by the finite-length paths through a finite labeled, directed graph. Karabed and Marcus (1988), extending the work of Adler, Coppersmith, and Hassner (1983), used the technique of state-splitting to prove the existence of a noncatastrophic, rate p:q finite-state encoder from binary data into S for any input word length p and codeword length q satisfying p/q/spl les/cap(S), the Shannon (1948) capacity. For constrained systems that are almost-finite-type, they further proved the existence of encoders enjoying a stronger form of decodability-namely, sliding-block decodability. In particular, their result implies the existence of a 100% efficient (rate 1/2), sliding-block code for the charge-constrained, runlength-limited constraint with parameters (d, k; c)=(1,3; 3), an almost-finite-type system with capacity precisely 1/2. We describe two quite different constructions of such codes. The constructions highlight connections between the problem of determining sliding-block decodability of a finite-state encoder and certain problems of colorability for graphs and sets. Using these connections, we show that the problem of determining the existence of a block-decodable input tag assignment for a given rate p:q, finite-state encoder is NP-complete, for p>1. We also prove NP-completeness results for several related problems in combinatorics and coding.