Periodic-Finite-Type Shift Spaces

Marie-Pierre Béal (1) , Maxime Crochemore (1) , Bruce Moision (2) , Paul Siegel (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Mathematical Sciences Research Center
3 Center for Magnetic Recording Research

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 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 G. From any periodic irreducible presentation of a given period, we define a periodic forbidden list, unique up to conjugacy 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 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.

Domaines: Algorithme et structure de données [cs.DS]

Marie-Pierre Béal, Maxime Crochemore, Bruce Moision, Paul Siegel. Periodic-Finite-Type Shift Spaces. IEEE Transactions on Information Theory, 2011, 57 (6), pp.3677-3691. ⟨hal-00619782⟩