Rationality and computability of the covering radius for sofic shifts
arXiv:2603.214493.2h-index: 13
Predicted impact top 92% in DS · last 90 daysOriginality Synthesis-oriented
AI Analysis
This addresses a theoretical problem in symbolic dynamics and information theory, with potential applications in data transmission, but it appears incremental as it builds on known concepts for sofic shifts.
The paper tackled the problem of determining the covering radius for sofic shifts, proving it is rational for primitive sofic shifts and providing an algorithm to compute it from a labeled graph presentation.
The covering radius of a shift space is a quantity of interest for information-theoretic applications of data transmission over noisy channels. We prove that the covering radius of a primitive sofic shift is a rational number, and describe an algorithm to compute the covering radius from a labeled graph presentation.