9 citations · 27 across the 17 of their papers we have counts for
5 papers · 1 filter
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…
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…
Infinite Communication Complexity
Pierre Guillon, Emmanuel Jeandel
Suppose that Alice and Bob are given each an infinite string, and they want to decide whether their two strings are in a given relation. How much communication do they need? How ca…
Densities and entropies in cellular automata
Pierre Guillon, Charalampos Zinoviadis
Following work by Hochman and Meyerovitch on multidimensional SFT, we give computability-theoretic characterizations of the real numbers that can appear as the topological entropie…
A compact topology for sand automata
Alberto Dennunzio, Pierre Guillon, Benoît Masson
In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology fo…