We study the class of periodic-finite-type (PFT) shift spaces, which can be used to model time-varying constrained codes used in digital magnetic recording systems. A PFT shift is determined by a finite list of periodically forbidden words. We show that the class of PFT shifts properly contains all finite-type (FT) shifts, and the class of almost finite-type (AFT) shifts properly contains all PFT shifts. We establish several basic properties of PFT shift spaces of a given period$T$, and provide a characterization of such a shift in terms of properties of its Shannon cover (i.e., its unique minimal, deterministic, irreducible graph presentation). We present an algorithm that, given the Shannon cover${\cal G}$of an irreducible sofic shift$X$, decides whether or not$X$is PFT in time that is quadratic in the number of states of${\cal G}$. From any periodic irreducible presentation of a given period, we define a periodic forbidden list, unique up to conjugacy (a circular permutation) for that period, that satisfies certain minimality properties. We show that an irreducible sofic shift is PFT if and only if the list corresponding to its Shannon cover${\cal G}$and its period is finite. Finally, we discuss methods for computing the capacity of a PFT shift from a periodic forbidden list, either by construction of a corresponding graph or in a combinatorial manner directly from the list itself.

A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Due to this synchronization property, these automata play an important role for coding purposes. We prove that any irreducible local automaton is contained in a complete one. The proof uses a result from symbolic dynamics due to M. Nasu called the masking lemma. A consequence of this result in the theory of variable length codes is that any locally parsable regular code is included in a maximal one with the same synchronisation delay.

We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The running time of the algorithm is O(min(m(n-r+1), m log n)), where m is the number of edges, n the number of states of the automaton, and r the number of states of the minimized automaton. In particular, the algorithm is linear when the automaton is already minimal and contrary to Hopcroft's minimization algorithm that has a O (kn log n) running time in this case, where k is the size of the alphabet, and that applies only to complete automata. (Note that kn ges m.) While Hopcroft's algorithm relies on a "negative strategy", starting from a partition with a single class of all states, and partitioning classes when it is discovered that two states cannot belong to the same class, our algorithm relies on a "positive strategy", starting from the trivial partition for which each class is a singleton. Two classes are then merged when their leaders have the same outputs. The algorithm applies to irreducible deterministic local automata, where all states are considered both initial and final. These automata, also called covers, recognize symbolic dynamical shifts of finite type. They serve to present a large class of constrained channels, the class of finite memory systems, used for channel coding purposes. The algorithm also applies to irreducible deterministic automata that are left-closing and have a synchronizing word. These automata present shifts that are called almost of finite type. Almost-of-finite-type shifts make a meaningful class of shifts, intermediate between finite type shifts and sofic shifts.

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.

The main result is a characterization of the generating sequences of the length of words in a regular language on k symbols. We say that a sequence s of integers is regular if there is a finite graph G with two vertices i, t such that s n is the number of paths of length n from i to t in G . Thus the generating sequence of a regular language is regular. We prove that a sequence s is the generating sequence of a regular language on k symbols if and only if both sequences s = ( s n ) n ≥0 and t = ( k n − s n ) n ≥0 are regular.

The method of poles is a method introduced by Franaszek (1969) for constructing a rate-1:1 finite-state code from k-ary data into a constrained channel of finite type whose capacity is strictly greater than log(k). The method is based on the computation of a set of states called poles. With each pole is associated a set of paths going from this pole to others. Each set verifies an entropy condition. The code produced by the method of poles has a sliding-block decoder if each set of paths satisfies moreover an optimization condition based on the sum of the path lengths of the set. We give a new optimization condition which guarantees the sliding-block window decoding property and has a lower computational complexity than the previous one. We also extend the method of poles to the more general case of sofic constrained channels.

The main result is a finite-state version of the Kraft--McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new construction called the multiset construction, which is a version with multiplicities of the well-known subset construction of automata theory.

published or not.The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.L'archive ouverte pluridisciplinaire

The method of poles is a method for constructing a rate 1:1 finite state code from K-ary data into a constrained channel S, where S is recognized by a given local automaton and S has capacity at least log(k). We characterize those automata to which the method of poles applies in the case where h(S)=log(k). The code produced by the method of poles has a sliding-block decoder. We also give an upper bound on the window length of the decoder that applies when h(S)/spl ges/log(k).>

A method for solving coding problems involving channels restricted by finite state constraints is presented. The method was introduced by P.A. Franaszek (1969) and is based on the computation of a set of principal states. It is proved that state-independent decoding is guaranteed. The main result is that the transducer constructed using the method is a local automaton in its output. The method is also related to recent work in symbolic dynamics by R.L. Adler (1987), B. Marcus (1985), and others. Typical applications are coding methods for magnetic storage.>