Cellular automata, quasigroups and symmetries

• Autores: A. Barbé, F. von Haeseler
• Localización: Aequationes mathematicae, ISSN 0001-9054, Vol. 62, Nº. 3, 2001, págs. 211-248
• Idioma: inglés
• DOI: 10.1007/pl00000149
• Texto completo no disponible (Saber más ...)
• Resumen

  • We investigate cellular automata (CA) with a local rule _boxclose G , where the local rule defines a quasigroup structure (Latin square) on the finite set G. If the quasigroup is semisymmetric or totally symmetric, some top-down equilateral triangular subsets of the CA-orbits, the so-called \triangledown -configurations, exhibit certain symmetries. The most interesting symmetries are the rotational and the total (dihedral) symmetries, which may be considered in conjunction with certain automorphisms.¶We first explore the conditions for quasigroups to be symmetric (or for local CA-rules to allow symmetric \triangledown -configurations), and how to construct symmetric quasigroups by prolongation, i.e., by steadily increasing the order of the quasigroup, thereby conserving the symmetry. Then we study rotationally or totally symmetric \triangledown -configurations. We begin with the existence of symmetric \triangledown -configurations of arbitrary size N and N º 0,1 mod 3, and show that symmetric \triangledown -configurations of size N º 2 mod 3 exist under mild conditions on J. We present explicit formulas for the number of distinct symmetric \triangledown -configurations. By studying the combined group action of the dihedral (or rotational) group and the automorphism group of the quasigroup G on the \triangledown -configurations of size N, we are able to classify and count the number of different equivalence classes of \triangledown -configurations.