## 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 under publication year if they have been published in a journal/proceedings, otherwise under submission year. See my DBLP entry or Google Scholar page for a more objective list.

- 2020
- 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

- Universal CA groups with few generators
- 2 pages

- Cutting Corners
- 44 pages
- play solitaire here

- A Physically Universal Turing Machine
- 2019
- Gardens of Eden in the Game of Life
- with Ilkka Törmä, 16 pages + 5 pages of code

- Trees in positive entropy subshifts
- 4 pages

- Recoding Lie algebraic subshifts
- with Ilkka Törmä, 18 pages

- 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

- Gardens of Eden in the Game of Life
- 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

- Universal gates with wires in a row
- 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, 31 pages
- accepted 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

- Decidability and Universality of Quasiminimal Subshifts
- 2016
- Subshifts with sparse traces
- 43 pages

- 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

- Subshifts with sparse traces
- 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

- Solving the Induced Subgraph problem in the randomized multiparty simultaneous messages model
- 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

- 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

- Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2
- 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

- Hard Asymptotic Sets for One-Dimensional Cellular Automata
- 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

- Realizing Subshifts as Sets of Surjective and Injective Nonuniform Cellular Automata (work-in-progress paper)
- 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

- A Survey on Picture-Walking Automata

### 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)
- More on winning shifts of substitutions (with Jarkko Peltomäki)