A1 Refereed original research article in a scientific journal
On countable SFT covers of sparse multidimensional shift spaces
Authors: Törmä, Ilkka
Publisher: Elsevier
Publication year: 2026
Journal: Theoretical Computer Science
Article number: 115755
Volume: 1066
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2026.115755
Publication's open availability at the time of reporting: Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.1016/j.tcs.2026.115755
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/509007498
Self-archived copy's licence: CC BY
Self-archived copy's version: Publisher`s PDF
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.
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
Author was supported by the Academy of Finland under grant 346566.
