13 citations · 15 across the 17 of their papers we have counts for
17 papers
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…
Avoshifts, Unishifts and Nondeterministic Cellular Automata
Ville Salo
In this paper, we study avoshifts and unishifts on . Avoshifts are subshifts where for each convex set , and each vector such that is also…
Symbol Frequencies in Surjective Cellular Automata
Benjamin Hellouin de Menibus, Ilkka Törmä, Ville Salo
We study the behavior of probability measures under iteration of a surjective cellular automaton. We solve the following question in the negative: if the initial measure is ergodic…
Nonexpansive chaotic almost minimal systems on residually finite groups
Ville Salo
The question of existence of nonexpansive chaotic almost minimal (CAM) systems, and the existence of CAM systems on every residually finite group, were raised in a recent paper of…
SFT covers for actions of the first Grigorchuk group
Rostislav Grigorchuk, Ville Salo
We study symbolic dynamical representations of actions of the first Grigorchuk group , namely its action on the boundary of the infinite rooted binary tree, its representation i…
Shifts on the lamplighter group
Laurent Bartholdi, Ville Salo
We prove that the lamplighter group admits strongly aperiodic SFTs, has undecidable tiling problem, and the entropies of its SFTs are exactly the upper semicomputable nonnegative r…