A1 Refereed original research article in a scientific journal
Countable Sofic Shifts with a Periodic Direction
Authors: Törmä I
Publisher: SPRINGER
Publication year: 2020
Journal: Theory of Computing Systems
Journal name in source: THEORY OF COMPUTING SYSTEMS
Journal acronym: THEOR COMPUT SYST
Volume: 64
Issue: 6
First page : 1042
Last page: 1066
Number of pages: 25
ISSN: 1432-4350
eISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-019-09962-8
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/44230050
Abstract
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.
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.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal