Slopes of Multidimensional Subshifts

Emmanuel Jeandel; Etienne Moutot; Pascal Vanier

doi:10.1007/s00224-019-09931-1

Slopes of Multidimensional Subshifts

Emmanuel Jeandel, Etienne Moutot, Pascal Vanier

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that Σ10 sets of non-commensurable ℤ² vectors are exactly the sets of slopes of 2D SFTs and that Σ20 sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.

Original language	English
Pages (from-to)	35-61
Number of pages	27
Journal	Theory of Computing Systems
Volume	64
Issue number	1
DOIs	https://doi.org/10.1007/s00224-019-09931-1
Publication status	Published - 1 Jan 2020
Externally published	Yes

Keywords

Computability
Periodicity
SFTs
Slopes
Subshifts

Access to Document

10.1007/s00224-019-09931-1

Cite this

@article{f5e84d5576824199b0392568151f29df,

title = "Slopes of Multidimensional Subshifts",

abstract = "In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that Σ10 sets of non-commensurable ℤ2 vectors are exactly the sets of slopes of 2D SFTs and that Σ20 sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.",

keywords = "Computability, Periodicity, SFTs, Slopes, Subshifts",

author = "Emmanuel Jeandel and Etienne Moutot and Pascal Vanier",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/s00224-019-09931-1",

language = "English",

volume = "64",

pages = "35--61",

journal = "Theory of Computing Systems",

issn = "1432-4350",

number = "1",

}

TY - JOUR

T1 - Slopes of Multidimensional Subshifts

AU - Jeandel, Emmanuel

AU - Moutot, Etienne

AU - Vanier, Pascal

PY - 2020/1/1

Y1 - 2020/1/1

N2 - In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that Σ10 sets of non-commensurable ℤ2 vectors are exactly the sets of slopes of 2D SFTs and that Σ20 sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.

AB - In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that Σ10 sets of non-commensurable ℤ2 vectors are exactly the sets of slopes of 2D SFTs and that Σ20 sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.

KW - Computability

KW - Periodicity

KW - SFTs

KW - Slopes

KW - Subshifts

U2 - 10.1007/s00224-019-09931-1

DO - 10.1007/s00224-019-09931-1

M3 - Article

AN - SCOPUS:85071461646

SN - 1432-4350

VL - 64

SP - 35

EP - 61

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -

Slopes of Multidimensional Subshifts

Abstract

Keywords

Access to Document

Fingerprint

Cite this