Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Dimension Sensitive Properties...

Dimension Sensitive Properties of Cellular Automata and Subshifts of Finite Type

Charalampos Zinoviadis, Dimension Sensitive Properties of Cellular Automata and Subshifts of Finite Type. TUCS Technical Reports 977, Turku Centre for Computer Science, 2010.

Abstract:

The topics of this technical report are dimension-sensitive properties of cellular automata and subshifts of finite type. Cellular automata are a well known model of parallel computation capturing the notions of locality and homogeneity in space and time, while subshifts of finite type can be used to study the geometric aspects of computation. Both cellular automata and subshifts of finite type are examples of symbolic dynamical systems. One-dimensional cellular automata and subshifts of finite type have been studied extensively and their properties are well understood. However, trying to generalize these properties to higher-dimensional cellular automata or subshifts of finite type is often impossible.

In particular, we are interested in recursion theoretic and dynamical system properties that are dimension sensitive. Approaching the subject through both points of view, we find out that many theorems holding in one-dimension are no longer true in the multidimensional cases, or are only true under much stronger conditions. For example, the decidability status of many problems turns from decidable in the one-dimensional case to undecidable when we go over to the multidimensional cases. In addition, topological entropy cannot give as satisfactory a classification for multidimensional symbolic systems as it gives for one-dimensional systems.

One of the aims of this thesis is to serve as a first reading for everyone that would like to know about this fascinating new area of symbolic dynamics. For this reason, we have included dimension sensitive properties originating from various points of view, and in many cases we have tried to give an intuitive explanation of what causes the difference between the one-dimensional and the mutlidimensional cases.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tZinoviadis10a,
  title = {Dimension Sensitive Properties of Cellular Automata and Subshifts of Finite Type},
  author = {Zinoviadis, Charalampos},
  number = {977},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2010},
  keywords = {multidimensional symbolic dynamics, dD subshifts of finite type, dimension sensitive properties of cellular automata, Nivat's conjecture},
  ISBN = {978-952-12-2434-8},
}

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

Edit publication