Periodic-Finite-Type Shift Spaces
- 23 May 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 57 (6) , 3677-3691
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 (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 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.Keywords
This publication has 28 references indexed in Scilit:
- Analytic Combinatorics2009
- A Comparative Study of Periods in a Periodic-Finite-Type ShiftSIAM Journal on Discrete Mathematics, 2009
- Tradeoff functions for constrained systems with unconstrained positionsIEEE Transactions on Information Theory, 2006
- Presentations of Constrained Systems With Unconstrained PositionsIEEE Transactions on Information Theory, 2005
- Constrained systems with unconstrained positionsIEEE Transactions on Information Theory, 2002
- Maximum runlength-limited codes with error control capabilitiesIEEE Journal on Selected Areas in Communications, 2001
- The Goulden—Jackson cluster method: extensions, applications and implementationsJournal of Difference Equations and Applications, 1999
- Symbolic Dynamics and Finite Automata1997
- An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished SubsequencesJournal of the London Mathematical Society, 1979
- Computing a graph's period quadratically by node condensationDiscrete Mathematics, 1973