On countable SFT covers of sparse multidimensional shift spaces




Törmä, Ilkka

PublisherElsevier

2026

 Theoretical Computer Science

115755

1066

0304-3975

1879-2294

DOIhttps://doi.org/10.1016/j.tcs.2026.115755

https://doi.org/10.1016/j.tcs.2026.115755

https://research.utu.fi/converis/portal/detail/Publication/509007498



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.


Author was supported by the Academy of Finland under grant 346566.


Last updated on 13/02/2026 08:52:08 AM