Skip to Main content Skip to Navigation
Journal articles

Periodic-Finite-Type Shift Spaces

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619782
Contributor : Marie-Pierre Béal <>
Submitted on : Wednesday, February 13, 2013 - 9:59:57 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:35 AM

File

Periodic-Finite-Type_Shift_Spa...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619782, version 1

Citation

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

Share

Metrics

Record views

376

Files downloads

328