On countable SFT covers of sparse multidimensional shift spaces
A multidimensional sofic shift is called countably covered if it has an SFT cover containing only countably many configurations. In contrast to the one-dimensional setting, not all countable sofic shifts are countably covered. We investigate the existence of countable covers for gap width shifts, where the number of nonzero symbols in a configuration is bounded by a function of the minimum distance between two such symbols. As our main results, we characterize those one-dimensional gap width shifts whose two-dimensional lift is a countably covered sofic shift, and show that a large class of two-dimensional gap width shifts are countably covered.
Authors
- Ilkka Törmä (ORCID: https://orcid.org/0000-0002-6056-9835)
Institutions
- University of Turku (FI)
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2026-01-15
- DOI
- https://doi.org/10.1016/j.tcs.2026.115755
- Primary Topic
- Cellular Automata and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00