9 papers
String attractors and bi-infinite words
Pierre Béaur, France Gheeraert, Benjamin Hellouin de Menibus
String attractors are a combinatorial tool coming from the field of data compression. It is a set of positions within a word which captures an occurrence of every factor. While one…
Undecidability of the block gluing classes of homshifts
Nishant Chandgotia, Silvère Gangloff, Benjamin Hellouin de Menibus +1
A homshift is a -dimensional shift of finite type which arises as the space of graph homomorphisms from the grid graph to a finite connected undirected graph .…
Parametrized complexity of relations between multidimensional subshifts
Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen
We study the parametrized complexity of fundamental relations between multidimensional subshifts, such as equality, conjugacy, inclusion, and embedding, for subshifts of finite typ…
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…
On the cohomology of homshifts
Nishant Chandgotia, Silvère Gangloff, Benjamin Hellouin de Menibus +1
We study the cohomology of symbolic dynamical systems called homshifts: they are the nearest-neighbour shifts of finite type whose adjacency rules are the same in ev…
Minimality and computability of languages of G-shifts
Djamel Eddine Amir, Benjamin Hellouin de Menibus
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for -shifts, where is a finitely generated…