Zobrazeno 1 - 10
of 43
pro vyhledávání: '"Vanier, Pascal"'
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, under some weak assumptions, this variant is undecidable regardless
Externí odkaz:
http://arxiv.org/abs/2409.11739
Autor:
Pavlov, Ronnie, Vanier, Pascal
We prove several results about the relationship between the word complexity function of a subshift and the set of Turing degrees of points of the subshift, which we call the Turing spectrum. Among other results, we show that a Turing spectrum can be
Externí odkaz:
http://arxiv.org/abs/1903.04325
This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly thi
Externí odkaz:
http://arxiv.org/abs/1808.09194
Autor:
Moutot, Etienne, Vanier, Pascal
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 of periodicity if it is periodic in exactly one direction, the slope b
Externí odkaz:
http://arxiv.org/abs/1806.07101
We consider the structure of aperiodic points in $\mathbb Z^2$-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a $\mathbb Z^2$-subshift contains points whose smallest period is arbitrarily large, then it
Externí odkaz:
http://arxiv.org/abs/1805.08829
Autor:
Vanier, Pascal
Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabi
Externí odkaz:
http://www.theses.fr/2012AIXM4813/document
Autor:
Hochman, Michael, Vanier, Pascal
Subshifts are shift invariant closed subsets of $\Sigma^{\mathbb{Z}^d}$ , minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing degree spectra of non-periodic minimal s
Externí odkaz:
http://arxiv.org/abs/1408.6487
Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of preimages. It is well known that these always contain a computable point
Externí odkaz:
http://arxiv.org/abs/1402.3766
Autor:
Jeandel, Emmanuel, Vanier, Pascal
We show that the sets of periods of multidimensional shifts of finite type (SFTs) are exactly the sets of integers of the complexity class $\NE$. We also show that the functions counting their number are the functions of #E. We also give characteriza
Externí odkaz:
http://arxiv.org/abs/1303.2462
Autor:
Emmanuel, Jeandel, Vanier, Pascal
We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension $d>1$. In particular, we prove that the factorization problem is $\Sigma^0_3$-complete and the conjugacy problem $\Sigma^0_1$-complete in
Externí odkaz:
http://arxiv.org/abs/1204.4988