• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Derivatives and Subpattern Orders of Countable Subshifts

Ville Salo, Ilkka Törmä, On Derivatives and Subpattern Orders of Countable Subshifts . In: Enrico Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, 23–36 , Open Publishing Association, 2012.

http://dx.doi.org/10.4204/EPTCS.90.3

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.

BibTeX entry:

@INPROCEEDINGS{inpSaTx12c,
  title = {On Derivatives and Subpattern Orders of Countable Subshifts },
  booktitle = {Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires},
  author = {Salo, Ville and Törmä, Ilkka},
  editor = {Formenti, Enrico},
  publisher = {Open Publishing Association},
  pages = {23–36 },
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication