Presentations of Constrained Systems With Unconstrained Positions
Marie-Pierre Béal, Maxime Crochemore, Gabriele Fici · IEEE Transactions on Information Theory · 2005
We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a linear-time construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type (PFT) systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for constructing the minimal periodic forbidden blocks of a finite sequence for a given period.