Decision problems on geometric tilings
Benjamin Hellouin de Menibus, Victor Lutfalla, Pascal Vanier
我们研究几何瓷砖的决策问题。 首先,我们研究多米诺骨牌问题的一个变体,其中方形瓷砖被任意形状的几何瓷砖所取代。 我们表明,无论形状如何,这种变体都是不可决定的,在rhombus瓷砖上扩展了以前的结果。 即使几何瓷砖被迫属于固定集,这一结果也会成立。 其次,我们考虑决定几何子移是否具有有限的地方复杂性的问题,这是研究几何图时常见的假设。 我们表明,即使在简单的设置(带有小修改的正方形形状)中,这个问题也是不可决定的。
We study decision problems on geometric tilings. First, we study a variant of the Domino problem where square tiles are replaced by geometric tiles of arbitrary shape. We show that this variant is undecidable regardless of the shapes, extending previous results on rhombus tiles. This result holds even when the geometric tiling is forced to belong to a fixed set. Second, we consider the problem of deciding whether a geometric subshift has finite local complexity, which is a common assumption when...