37 citations · 53 across the 16 of their papers we have counts for
20 papers
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…
Limit dynamics of elementary cellular automaton 18
Hervé Sabrié, Ilkka Törmä
We study the the asymptotic dynamics of elementary cellular automaton 18 through its limit set, generic limit set and -limit set. The dynamics of rule 18 are characterized by pe…
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)…
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…
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…
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…
PSPACE-Completeness of Majority Automata Networks
Eric Goles, Pedro Montealegre, Ville Salo +1
We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the…
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…
Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2
Ville Salo, Ilkka Törmä
In this article, we study countable sofic shifts of Cantor-Bendixson rank at most 2. We prove that their conjugacy problem is complete for GI, the complexity class of graph isomorp…
Subshifts, MSO Logic, and Collapsing Hierarchies
Ilkka Törmä
We use monadic second-order logic to define two-dimensional subshifts, or sets of colorings of the infinite plane. We present a natural family of quantifier alternation hierarchies…
Trace Complexity of Chaotic Reversible Cellular Automata
Jarkko Kari, Ville Salo, Ilkka Törmä
Delvenne, Kůrka and Blondel have defined new notions of computational complexity for arbitrary symbolic systems, and shown examples of effective systems that are computationally un…
Quantifier Extensions of Multidimensional Sofic Shifts
Ilkka Törmä
We define a pair of simple combinatorial operations on subshifts, called existential and universal extensions, and study their basic properties. We prove that the existential exten…
Constructions with Countable Subshifts of Finite Type
Ville Salo, Ilkka Törmä
We present constructions of countable two-dimensional subshifts of finite type (SFTs) with interesting properties. Our main focus is on properties of the topological derivatives an…
Playing with Subshifts
Ville Salo, Ilkka Törmä
We study the class of word-building games, where two players pick letters from a finite alphabet to construct a finite or infinite word. The outcome is determined by whether the re…
A Uniquely Ergodic Cellular Automaton
Ilkka Törmä
We construct a one-dimensional uniquely ergodic cellular automaton which is not nilpotent. This automaton can perform asymptotically infinitely sparse computation, which neverthele…
Category Theory of Symbolic Dynamics
Ville Salo, Ilkka Törmä
We study the central objects of symbolic dynamics, that is, subshifts and block maps, from the perspective of basic category theory, and present several natural categories with sub…
Block Maps between Primitive Uniform and Pisot Substitutions
Ville Salo, Ilkka Törmä
In this article, we prove that for all pairs of primitive Pisot or uniform substitutions with the same dominating eigenvalue, there exists a finite set of block maps such that ever…
Geometry and Dynamics of the Besicovitch and Weyl Spaces
Ville Salo, Ilkka Törmä
We study the geometric properties of Cantor subshifts in the Besicovitch space, proving that sofic shifts occupy exactly the homotopy classes of simplicial complexes. In addition,…
On Shift Spaces with Algebraic Structure
Ville Salo, Ilkka Törmä
We investigate subshifts with a general algebraic structure and cellular automata on them, with an emphasis on (order-theoretic) lattices. Our main results concern the characteriza…