Constructions with Countable Subshifts of Finite Type

Issue title: Cellular Automata and Models of Computation

Article type: Research Article

Authors: Salo, Ville^; | Törmä, Ilkka^;

Affiliations: TUCS – Turku Centre for Computer Science, Finland | University of Turku, Finland. vosalo@utu.fi | University of Turku, Finland, iatorm@utu.fi

Note: [] Address for correspondence: TUCS – Turku Centre for Computer Science, Finland, University of Turku, Finland

Abstract: 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 and subpattern posets of these objects. We present a countable SFT whose iterated derivatives are maximally complex from the computational point of view, constructions of countable SFTs with high Cantor-Bendixson ranks, a countable SFT whose subpattern poset contains an infinite descending chain and a countable SFT whose subpattern poset contains all finite posets. When possible, we make these constructions deterministic, and ensure the sets of rows are very simple as one-dimensional subshifts.

Keywords: countable subshifts, Cantor-Bendixson rank, subpattern poset

DOI: 10.3233/FI-2013-881

Journal: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 263-300, 2013