A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
On Derivatives and Subpattern Orders of Countable Subshifts
Tekijät: Ville Salo, Ilkka Törmä
Toimittaja: Enrico Formenti
Julkaisuvuosi: 2012
Journal: Electronic Proceedings in Theoretical Computer Science
Kokoomateoksen nimi: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires
Sarjan nimi: Electronic Proceedings in Theoretical Computer Science
Aloitussivu: 23
Lopetussivu: 36
ISSN: 2075-2180
DOI: https://doi.org/10.4204/EPTCS.90.3
Tiivistelmä
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.
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali