45 citations · 158 across the 57 of their papers we have counts for
76 papers
Conjugacy problems in higher-dimensional Thompson groups
Ville Salo
We prove that topological conjugacy of elements of the Brin--Thompson group is undecidable for every . From a Turing machine , the reduction produces two elements o…
Thinking outside the box is useless NFA = FNFA
Maxence Ponsardin, Ville Salo
We study picture-walking automata, namely finite-state automata that accept higher-dimensional parallelotope-/tensor-shaped pictures and are allowed to move in all directions depen…
A Three-Dimensional SFT with Sparse Columns
Ville Salo, Ilkka Törmä
We construct a nontrivial three-dimensional subshift of finite type whose projective -subdynamics, or -trace, is 2-sparse, meaning that there are at most two nonzero symbol…
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…
Topological entropy of Turing complete dynamics
Renzo Bruera, Robert Cardona, Eva Miranda +2
We explore the relationship between Turing completeness and topological entropy of dynamical systems. We first prove that a natural class of Turing machines that we call "branching…
On the growth of actions of free products
Adrien Le Boudec, Nicolás Matte Bon, Ville Salo
If is a finitely generated group and a -set, the growth of the action of on is the function that measures the largest cardinality of a ball of radius in the…
Structure and computability of preimages in the Game of Life
Ville Salo, Ilkka Törmä
Conway's Game of Life is a two-dimensional cellular automaton. As a dynamical system, it is well-known to be computationally universal, i.e.\ capable of simulating an arbitrary Tur…
Diddy: a Python toolbox for infinite discrete dynamical systems
Ville Salo, Ilkka Törmä
We introduce Diddy, a collection of Python scripts for analyzing infinite discrete dynamical systems. The main focus is on generalized multidimensional shifts of finite type (SFTs)…
Wreath products in the automorphism group of a full shift
Ville Salo
We prove that if a subgroup of the automorphism group $\Aut(Σ^\Z)$ of a non-trivial full shift acts on points of finite support (= points bi-asymptotic to a fixed point) with a…
The group of reversible Turing machines: subgroups, generators and computability
Sebastián Barbieri, Jarkko Kari, Ville Salo
We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and…
Finding codes on infinite grids automatically
Ville Salo, Ilkka Törmä
We apply automata theory and Karp's minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound $53/126 \approx…
On von Neumann regularity of cellular automata
Ville Salo
We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only i…
Distortion element in the automorphism group of a full shift
Antonin Callard, Ville Salo
We show that there is a distortion element in a finitely-generated subgroup of the automorphism group of the full shift, namely an element of infinite order whose word norm gro…
Triangle solitaire
Ville Salo, Juliette Schabanel
The solitaire of independence is a groupoid action resembling the classical 15-puzzle, which gives information about independent sets of coordinates in a totally extremally permuti…
Automorphism groups of random substitution subshifts
Robbert Fokkink, Dan Rust, Ville Salo
We prove that for a suitably nice class of random substitutions, their corresponding subshifts have automorphism groups that contain an infinite simple subgroup and a copy of the a…
What can oracles teach us about the ultimate fate of life?
Ville Salo, Ilkka Törmä
We settle two long-standing open problems about Conway's Life, a two-dimensional cellular automaton. We solve the Generalized grandfather problem: for all , there exists…
Cellular Automata and Bootstrap Percolation
Ville Salo, Guillaume Theyssier, Ilkka Törmä
We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the…
Automatic winning shifts
Jarkko Peltomäki, Ville Salo
To each one-dimensional subshift , we may associate a winning shift which arises from a combinatorial game played on the language of . Previously it has been studied w…
Sofically presented dynamical systems
Johan Kopra, Ville Salo
Systems obtained by quotienting a subshift of finite type (SFT) by another SFT are called finitely presented in the literature. Analogously, if a sofic shift is quotiented by a sof…
Thompson's in MCG of mixing SFT by PW-linear homeos
Ville Salo
In a recent paper, we showed that groups admitting "veelike actions" on a finite language embed in mapping class groups of certain two-sided subshifts. In this note, we illustrate…
Conjugacy of transitive SFTs minus periodic points
Ville Salo
It is a question of Hochman whether any two one-dimensional topologically mixing subshifts of finite type (SFTs) with the same entropy are topologically conjugate when their period…
Self-simulable groups
Sebastián Barbieri, Mathieu Sablik, Ville Salo
We say that a finitely generated group is self-simulable if every effectively closed action of on a closed subset of is the topolog…
Veelike actions and the MCG of a mixing SFT
Ville Salo
We embed Thompson's group in the mapping class group of a mixing subshift of finite type. Question~6.3 in [Boyle-Chuysurichay, 17] asks whether these mapping class groups are s…
Graph and wreath products in topological full groups of full shifts
Ville Salo
We prove that the topological full group of a two-sided full shift contains every right-angled Artin group (also called a graph group). More generally,…