T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures

摘要

In this paper, processes occuring in homogeneous, deterministic, d-dimensional tessellation structures (cellular automata) are shown to be equivalent to a special kind of recognition of a special type of d-dimensional formal languages. It is called “T-recognition of T-languages” where T stands for “template”. In order to treat T-recognizability of T-languages, a mathematically closed and notationally simple theory is developed whose basic ideas are exhibited. Some necessary conditions for T-recognizability are presented which can be used to prove non-T-recognizability. On the other hand, a sufficient condition is given, which can guide the cellular automata theory researcher where to look for transition functions, allows the construction of the appropriate tessellation structure, and proves that it functions well. It can be used to design tessellation structures in a recursive top-down manner.