4 papers
On surjunctive and injunctive subshifts of finite type
Tullio Ceccherini-Silberstein, Michel Coornaert, Ville Salo
A dynamical system is said to be surjunctive if every injective endomorphism of the system is surjective and it is said to be injunctive if every surjective endomorphism is injecti…
Self-simulability of graph products
Kanéda Blot, Ville Salo
A group is self-simulable if all its computable actions admit SFT covers, which means roughly that they can be implemented with finitely many tiling constraints. We prove that a gr…
Descriptive Complexity of Sensitivity of Cellular Automata
Tom Favereau, Ville Salo
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is -complete in dimension 1 a…
Word problems and embedding-obstructions in cellular automata groups on groups
Ville Salo
We study groups of reversible cellular automata, or CA groups, on groups. More generally, we consider automorphism groups of subshifts of finite type on groups. It is known that wo…