Scholarlink

We study the notion of full-compatibility: given two one-dimensional subshifts H and V, is there a two-dimensional subshift X such that \({H = \{c_{\mid \mathbb {Z}\times \{0\}} \mid c \in X\}}\) and \({V =\{c_{\mid \{0\}\times \mathbb {Z}} \mid c \in X\}}\) ? We show that this problem is decidable when both X and Y are nearest-neighbor SFTs but undecidable when at least one is allowed to be of slightly higher complexity. We also prove that the problem is undecidable for three nearest-neighbor SFTs combined in a three-dimensional subshift.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Vertical-Horizontal Full Compatibility of One-Dimensional Subshifts

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Arthur Mittelstaedt,
  • Gaétan Richard

摘要

We study the notion of full-compatibility: given two one-dimensional subshifts H and V, is there a two-dimensional subshift X such that \({H = \{c_{\mid \mathbb {Z}\times \{0\}} \mid c \in X\}}\) and \({V =\{c_{\mid \{0\}\times \mathbb {Z}} \mid c \in X\}}\) ? We show that this problem is decidable when both X and Y are nearest-neighbor SFTs but undecidable when at least one is allowed to be of slightly higher complexity. We also prove that the problem is undecidable for three nearest-neighbor SFTs combined in a three-dimensional subshift.