5 papers
Pattern Complexity of Aperiodic Substitutive Subshifts
Etienne Moutot, Coline Petit-Jean
This paper aims to better understand the link better understand the links between aperiodicity in subshifts and pattern complexity. Our main contribution deals with substitutive su…
Computational Limitations of Affine Automata
Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryılmaz
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-values affine automata is simulated in…
The domino problem is undecidable on surface groups
Nathalie Aubrun, Sebastián Barbieri, Etienne Moutot
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino pr…
Nivat's Conjecture and Pattern Complexity in Algebraic Subshifts
Jarkko Kari, Etienne Moutot
We study Nivat's conjecture on algebraic subshifts and prove that in some of them every low complexity configuration is periodic. This is the case in the Ledrappier subshift (the 3…
Slopes of 3-dimensional Subshifts of Finite Type
Etienne Moutot, Pascal Vanier
In this paper we study the directions of periodicity of three-dimensional subshifts of finite type (SFTs) and in particular their slopes. A configuration of a subshift has a slope…