9 citations · 27 across the 17 of their papers we have counts for
19 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…
Dill maps in the Weyl-like space associated to the Levenshtein distance
Firas Ben Ramdhane, Pierre Guillon
The Weyl pseudo-metric is a shift-invariant pseudo-metric over the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of cellul…
Graph subshifts
Pablo Arrighi, Amélia Durbec, Pierre Guillon
We propose a definition of graph subshifts of finite type that can be seen as extending both the notions of subshifts of finite type from classical symbolic dynamics and finitely p…
Hardness of monadic second-order formulae over succinct graphs
Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon +3
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graph…
Cellular automata and substitutions in topological spaces defined via edit distances
Firas Ben Ramdhane, Pierre Guillon
The Besicovitch pseudo-metric is a shift-invariant pseudo-metric on the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of c…
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…