Countable Sofic Shifts with a Periodic Direction



: Törmä I

Publisher: SPRINGER

: 2020

: Theory of Computing Systems

: THEORY OF COMPUTING SYSTEMS

: THEOR COMPUT SYST

: 64

: 6

: 1042

: 1066

: 25

: 1432-4350

: 1433-0490

DOI: https://doi.org/10.1007/s00224-019-09962-8

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


As a variant of the equal entropy cover problem, we ask whether all multidimensional sofic shifts with countably many configurations have SFT covers with countably many configurations. We answer this question in the negative by presenting explicit counterexamples. We formulate necessary conditions for a vertically periodic shift space to have a countable SFT cover, and prove that they are sufficient in a natural (but quite restricted) subclass of shift spaces.

Last updated on 2024-26-11 at 12:23