This chapter attempts to reconcile two popular topologies that seem incompatible in two–dimensional cellular automata (CA), namely the two topologies whose base cell is either the hexagon or the square. A detailed study of regular tilings of the infinite plane is first presented although it is a well–known concept. It highlights aspects that are sometimes approached in a confusing manner and defines the relationships between the coordinate systems used. The second part is devoted to the choice of the topology for a finite framework with the appropriate boundary conditions. Two fundamental patterns, the propeller and the bee, emerge among the seven possible tetrahexes. These two patterns induce the generating set of a reproducible tiling. The result is a family of Cayley graphs, the arrowhead and the diamond, isomorphic in their undirected version. Their morphism is the key unifying the hexagon and the square. Such a CA network is a good host for embedding well–known topologies like T–tree or B–tree. It is also suitable for the study of self–similarity in nature and physics, fractal structures and renormalization procedures.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Versatile Topology for Two–Dimensional Cellular Automata

  • Dominique Désérable

摘要

This chapter attempts to reconcile two popular topologies that seem incompatible in two–dimensional cellular automata (CA), namely the two topologies whose base cell is either the hexagon or the square. A detailed study of regular tilings of the infinite plane is first presented although it is a well–known concept. It highlights aspects that are sometimes approached in a confusing manner and defines the relationships between the coordinate systems used. The second part is devoted to the choice of the topology for a finite framework with the appropriate boundary conditions. Two fundamental patterns, the propeller and the bee, emerge among the seven possible tetrahexes. These two patterns induce the generating set of a reproducible tiling. The result is a family of Cayley graphs, the arrowhead and the diamond, isomorphic in their undirected version. Their morphism is the key unifying the hexagon and the square. Such a CA network is a good host for embedding well–known topologies like T–tree or B–tree. It is also suitable for the study of self–similarity in nature and physics, fractal structures and renormalization procedures.