9 papers
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…
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 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…
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…
Graph and wreath products of cellular automata
Ville Salo
We prove that the set of subgroups of the automorphism group of a two-sided full shift is closed under countable graph products. We introduce the notion of a group action without $…
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…