.png){kind=icon}
.png){kind=icon}
Return
The Capacities of Periodic-Finite-Type Shifts from the Perspective of the Forbidden-Word Length
.png){kind=icon}
PRE
AI
M
N
R
T
DOI：10.1587/transfun.2025EAP1099.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A Periodic-Finite-Type shift (PFT) is a set of bi-infinite sequences that prohibit the appearance of forbidden words in a periodic manner. More precisely, a PFT X-{T,X- F(sic)} is a set of bi-infinite sequences x characterized by a period T is an element of N and a family F(sic) = (F(sic)((0)), F(sic)((1)), & centerdot;& centerdot;& centerdot;, F(sic)((T-1))) of indexed finite sets of forbidden words F(sic)((0)),F(sic)((1)), & centerdot;& centerdot;& centerdot;, F(sic)((T-1)), so that the r-shifted sequence sigma (R)(x) of x does not contain words in F(sic)((i mod T)) at position i is an element of Z. The study on PFTs is strongly related to the study on constrained systems with unconstrained positions, which have the property as both error-correcting codes and constrained codes. The capacity of a PFT is an important value that gives us the maximum coding rate when a random sequence is encoded to a sequence in the PFT. In this paper, we derive the capacity of a PFT in two ways, using the fact that an arbitrary family is transformed into a family F = (F-(0), & empty; & centerdot;& centerdot;& centerdot;, & empty;), where each forbidden word in F-(0) has the same length k, so that X-{T,X-F(sic)} = X-{T,X-F}. When k <= T, the first proof derives the capacity directly from the definition, and the other proof does from block partitioning of the adjacency matrix of a certain graph representing X-{T,X-F}. We also present a partial result on the capacity when k > T.
Keywords:
periodic-finite-type shift
sofic shift
capacity
period
the length of forbidden words
Journal
IF:
0.4
Papers:
182
Citations:
1.3K
Organization
Cited Papers