Complexity and sliding-block decidability

A constrained system, or soflc system, S is the set of symbol strings generated by the finite-length paths through a finite labeled, directed graph. Karabed and Marcus, extending the work of Adler, Coppersmith, and Hassner, used the technique of state-splitting to prove the existence of a noncatastrophic, rate p : q finite-state encoder from binary data into 5 for any input word length p and codeword length q satisfying p/q < cap (S), the Shannon 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. In this paper, 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 blockdecodable input tag assignment for a given rate p, finite-state encoder is NP-complete, for p > 1. We also prove NP-completeness results for several related problems in combinatorics and coding. © 1996 IEEE.