45 citations · 158 across the 57 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
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…
Von Neumann regularity, split epicness and elementary cellular automata
Ville Salo
We show that a cellular automaton on a mixing subshift of finite type is a Von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto it…
On winning shifts of marked uniform substitutions
Jarkko Peltomäki, Ville Salo
The second author introduced with I. Törmä a two-player word-building game [Playing with Subshifts, Fund. Inform. 132 (2014), 131--152]. The game has a predetermined (possibly fini…
A One-Dimensional Physically Universal Cellular Automaton
Ville Salo, Ilkka Törmä
Physical universality of a cellular automaton was defined by Janzing in 2010 as the ability to implement an arbitrary transformation of spatial patterns. In 2014, Schaeffer gave a…
Plane-Walking Automata
Ville Salo, Ilkka Törmä
In this article, we study classes of multidimensional subshifts defined by multihead finite automata, in particular the hierarchy of classes of subshifts defined as the number of h…