On Derivatives and Subpattern Orders of Countable Subshifts

2012/08/13 by Ville Salo, Ilkka Törmä · 1 citation
Computer Science · Mathematics · #Cellular Automata and Applications #Chain (unit) #Combinatorics #Countable set #Discrete mathematics #Focus (optics) #Iterated function #Mathematical Dynamics and Fractals #Mathematical analysis #Mathematics #Pure mathematics #Rank (graph theory) #cs.CC #semigroups and automata theory

paper · pdf · doi:10.4204/eptcs.90.3

published as EPTCS 90, 2012, pp. 23-36 · In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

openalex publication_date 2012/08/13 · arxiv created 2012/08/14 · arxiv updated 2012/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We study the computational and structural aspects of countable two-dimensional SFTs and other subshifts. Our main focus is on the topological derivatives and subpattern posets of these objects, and our main results are constructions of two-dimensional countable subshifts with interesting properties. We present an SFT whose iterated derivatives are maximally complex from the computational point of view, a sofic shift whose subpattern poset contains an infinite descending chain, a family of SFTs whose finite subpattern posets contain arbitrary finite posets, and a natural example of an SFT with infinite Cantor-Bendixon rank.

Citations

• Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires
• Endomorphisms and automorphisms of the shift dynamical system
• The undecidability of the domino problem
• Undecidability and nonperiodicity for tilings of the plane

Cited by

• Constructions with Countable Subshifts of Finite Type