37 citations · 53 across the 16 of their papers we have counts for
13 papers · 1 filter
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…
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…