Ville Salo

Publications

The names, contents and existence of the articles in the following list may differ from actual publications, and the linked version may not be the published version. Articles are either under publication year or under submission year. See my DBLP entry or Google Scholar page for a more objective list.

2023
- Finding codes on infinite grids automatically
  - with Ilkka Törmä, 17 pages.
  - Scripts available on GitHub.
2022
- On von Neumann regularity of cellular automata
  - 16 pages.
  - Scripts available on Zenodo.
- Distortion element in the automorphism group of a full shift
  - with Antonin Callard, 52 pages.
- Triangle solitaire
  - with Juliette Schabanel, 12+2 pages.
- Gate lattices
  - 20 pages.
- Automorphism groups of random substitution subshifts
  - with Robbert Fokkink and Dan Rust, 29 pages.
- What can oracles teach us about the ultimate fate of life?
  - with Ilkka Törmä, 18 pages.
  - See also the GitHub repo.
2021
- Cellular Automata and Bootstrap Percolation
  - with Guillaume Theyssier and Ilkka Törmä, 18 pages.
- Automatic winning shifts
  - with Jarkko Peltomäki, 28 pages.
- Sofically presented dynamical systems
  - with Johan Kopra, 56 pages + 5 pages of appendices.
- Conjugacy of transitive SFTs minus periodics
  - 7 pages
- Groups with self-simulable zero-dimensional dynamics
  - with Sebastián Barbieri and Mathieu Sablik, 54 pages
- Thompson's V in MCG of mixing SFT by PW-linear homeos
  - 5 pages, 10 pages of diagrams, 6 pages of Python
- Veelike actions and the MCG of a mixing SFT
  - 5 pages
- Graph and wreath products in topological full groups of full shifts
  - 11 pages
2020
- Graph and wreath products of cellular automata
  - 20 pages
- Simulations and the Lamplighter Group
  - 46 pages
- Conjugacy of reversible cellular automata and one-head machines
  - 37 pages
- Examples of Non-Busemann Horoballs
  - 22 pages
- A Physically Universal Turing Machine
  - with Ilkka Törmä, 45 pages + 5 pages of @RULE + 1 page of Lua
- Four heads are better than three
  - 14 pages
  - presented in AUTOMATA 2020
- Universal CA groups with few generators
  - 2 pages
- Cutting Corners
  - 54 pages
  - play solitaire here
2019
- Gardens of Eden in the Game of Life
  - with Ilkka Törmä, 16 pages + 5 pages of code
- Trees in positive entropy subshifts
  - 8 pages
- Recoding Lie algebraic subshifts
  - with Ilkka Törmä, 18 pages
  - errata here
- Trees are nilrigid
  - 6 pages
- Entropy pair realization
  - 15 pages
- A note on directional closing
  - 4 pages
- Alternation diameter of a product object
  - 23 pages
- On winning shifts of marked uniform substitutions
  - with Jarkko Peltomäki, 17 pages
  - published in RAIRO - Theoretical Informatics and Applications
  - short version presented in RuFiDiM 2017
2018
- Universal gates with wires in a row
  - 15 pages + 3 page appendix
  - Try to not
- Minimal subshift with a language pivot property
  - 6 pages
- Universal Groups of Cellular Automata
  - 34 pages
- When are group shifts of finite type?
  - 8 pages
- Nilpotent Endomorphisms of Expansive Group Actions
  - with Ilkka Törmä, 54 pages
- Von Neumann regularity, split epicness and elementary cellular automata
  - 13 pages + appendix.
  - Accompanying Python scripts: checking rules and checking numbers
- Sequentializing cellular automata
  - with Jarkko Kari and Thomas Worsch, 23 pages
  - accepted in AUTOMATA 2018
- No Tits alternative for cellular automata
  - 16 pages
  - accepted in Groups, Geometry and Dynamics
2017
- Decidability and Universality of Quasiminimal Subshifts
  - 57 pages
  - accepted in Journal of Computer and System Sciences
  - errata/notes here
- Strict Asymptotic Nilpotency in Cellular Automata
  - 13 pages
  - presented in AUTOMATA 2017 as invited talk, 13 pages
  - slides here
- Characterizing Asymptotic Randomization in Abelian Cellular Automata
  - with Benjamin Hellouin de Menibus and Guillaume Theyssier, 33 pages
  - published in Ergodic Theory and Dynamical Systems
- On Pointwise Periodicity in Tilings, Cellular Automata and Subshifts
  - with Tom Meyerovitch, 23 pages
  - accepted in Groups, Geometry and Dynamics
- A One-Dimensional Physically Universal Cellular Automaton
  - with Ilkka Törmä, 17 pages
  - accepted in Computability in Europe 2017
- Transitive action on finite points of a full shift and a finitary Ryan’s theorem
  - 35 pages
  - accepted in Ergodic Theory and Dynamical Systems
  - notes here
- Finite generating sets for reversible gate sets under general conservation laws
  - with Tim Boykett and Jarkko Kari, 26 pages
  - accepted in Theoretical Computer Science
- Distortion in One-Head Machines and Cellular Automata
  - with Pierre Guillon, 19 pages
  - presented in AUTOMATA 2017
- Independent finite automata on Cayley graphs
  - with Ilkka Törmä, 16 pages
  - published in Natural Computing
2016
- Subshifts with sparse traces
  - 43 pages
  - Accepted in Studia Mathematica
- The group of reversible Turing machines
  - with Sebastián Barbieri and Jarkko Kari, 26 pages
  - presented in AUTOMATA 2016
- Strongly Universal Reversible Gate Sets
  - with Tim Boykett and Jarkko Kari, 16 pages
  - presented in Reversible Computation 2016
- Distributed Testing of Excluded Subgraphs
  - with Pierre Fraigniaud, Ivan Rapaport and Ioan Todinca, 16 pages
  - accepted to DISC, 2016
- A note on subgroups of automorphism groups of full shifts
  - 12 pages
  - accepted in Ergodic Theory and Dynamical Systems
  - notes here
- PSPACE-Completeness of Majority Automata Networks
  - with Eric Goles, Pedro Montealegre and Ilkka Törmä, 14 pages
  - published in Theoretical Computer Science
- Toeplitz subshift whose automorphism group is not finitely generated
  - 22 pages
  - accepted in Colloquium Mathematicum
2015
- Solving the Induced Subgraph problem in the randomized multiparty simultaneous messages model
  - with Jarkko Kari, Martin Matamala and Ivan Rapaport, 14 pages
  - accepted in SIROCCO 2015
- Groups and monoids of cellular automata
  - 29 pages
  - presented in AUTOMATA 2015 as invited talk
  - errata/notes here
- Group-Walking Automata
  - with Ilkka Törmä, 14 pages
  - presented in AUTOMATA 2015
- Category Theory of Symbolic Dynamics
  - with Ilkka Törmä, 45 pages
  - published in Theoretical Computer Science
- Factor Colorings of Linearly Recurrent Words
  - with Ilkka Törmä, 7 pages
  - notes here
2014
- Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2
  - with Ilkka Törmä, 14 pages
  - presented in AUTOMATA 2014
- Plane-Walking Automata
  - with Ilkka Törmä, 17 pages
  - presented in AUTOMATA 2014
- Trace Complexity of Chaotic Reversible Cellular Automata
  - with Jarkko Kari and Ilkka Törmä, 13 pages
  - presented in Reversible Computing 2014
- Realization Problems for Nonuniform Cellular Automata
  - 21 pages
  - published in Theoretical Computer Science
  - extended version of Realizing Subshifts as Sets of Surjective and Injective Nonuniform Cellular Automata
  - errata here
- Block Maps between Primitive Uniform and Pisot Substitutions
  - with Ilkka Törmä, 21 pages
  - published in Ergodic Theory and Dynamical Systems
- Color Blind Cellular Automata
  - with Ilkka Törmä, 28 pages
  - published in Journal of Cellular Automata
2013
- Hard Asymptotic Sets for One-Dimensional Cellular Automata
  - 6 pages
- Surjective Two-Neighbor Cellular Automata on Prime Alphabets
  - with Jarkko Kari and Ilkka Törmä, 8 pages
  - presented in AUTOMATA 2013
  - notes here
- Commutators of Bipermutive and Affine Cellular Automata
  - with Ilkka Törmä, 16 pages
  - presented in AUTOMATA 2013
- Color Blind Cellular Automata
  - with Ilkka Törmä, 14 pages
  - presented in AUTOMATA 2013
- Constructions with Countable Subshifts of Finite Type
  - with Ilkka Törmä, 38 pages
  - extended version of On Derivatives and Subpattern Orders of Countable Subshifts
  - published in Fundamenta Informaticae
  - errata here
- Playing with Subshifts
  - with Ilkka Törmä, 22 pages
  - published in Fundamenta Informaticae
2012
- Realizing Subshifts as Sets of Surjective and Injective Nonuniform Cellular Automata (work-in-progress paper)
  - 8 pages
  - presented in RuFiDiM 2012 as a work-in-progress paper
- Playing with Subhifts (work-in-progress paper)
  - with Ilkka Törmä, 8 pages
  - presented in RuFiDiM 2012 as a work-in-progress paper
- On Nilpotency and Asymptotic Nilpotency of Cellular Automata
  - 11 pages
  - presented in Automata/JAC 2012
- Topology Inspired Problems for Cellular Automata, and a Counterexample in Topology
  - with Ilkka Törmä, 19 pages
  - presented in Automata/JAC 2012
- On Derivatives and Subpattern Orders of Countable Subshifts
  - with Ilkka Törmä, 15 pages
  - presented in Automata/JAC 2012
- Computational Aspects of Cellular Automata on Countable Sofic Shifts
  - with Ilkka Törmä, 13 pages
  - presented in MFCS 2012 by Ilkka
  - errata here
- Geometry and Dynamics of the Besicovitch and Weyl Spaces
  - with Ilkka Törmä, 15 pages
  - presented in DLT 2012 as a short paper
- On Shift Spaces with Algebraic Structure
  - with Ilkka Törmä, 12 pages
  - presented in CiE 2012
- A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
  - 12 pages
  - presented in CSR 2012
- On Stable and Unstable Limit Sets of Finite Families of Cellular Automata
  - with Ilkka Törmä, 12 pages
  - presented in LATA 2012
2011
- A Survey on Picture-Walking Automata
  - with Jarkko Kari, 31 pages
  - appeared in Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement

Some works in progress

I list some ongoing projects here. This is a partial list, roughly in decreasing order of age, of projects with other people where there are (in my opinion) enough results for at least one publication, and where my plan is to finish a preprint within a reasonable time frame. The list has not necessarily been approved by coauthors mentioned. All titles are subject to change. Solo projects and projects with Ilkka Törmä mostly not listed.

Automorphism groups of subshifts via group extensions (with Michael Schraudner)
The group of reversible Turing machines: subgroups, generators and computability (with Sebastián Barbieri and Jarkko Kari)
SFTs with Sparse Columns (with Ilkka Törmä)
Systems of horoballs (with Enrico le Donne and Thibaut Dumont)