2 citations · 6 across the 12 of their papers we have counts for
16 papers
Pimp my fixpoint: sofic realization of multidimensional substitution-based shift spaces
Antonin Callard, Pierre Guillon, Léo Paviet Salomon +1
In symbolic dynamics, the fixed-point construction from arXiv:0910.2415 defines shift spaces of finite type whose configurations embed infinite hierarchies of tilings. This article…
Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
Antonin Callard, Andrei Romashchenko, Véronique Terrier +1
We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et…
Decision problems on geometric tilings
Benjamin Hellouin de Menibus, Victor Lutfalla, Pascal Vanier
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…
Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
Antonin Callard, Léo Paviet Salomon, Pascal Vanier
Subshifts are sets of colorings of defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of all its admissi…
The relationship between word complexity and computational complexity in subshifts
Ronnie Pavlov, Pascal Vanier
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…
Undecidable word problem in subshift automorphism groups
Pierre Guillon, Emmanuel Jeandel, Jarkko Kari +1
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 aut…