Affiliations: Iwakura Miyake-cho 204, Sakyo-ku, 606-0022 Kyoto, Japan.
E-mail: [email protected] | LITA, EA 3097, UFR MIM, University of Metz, Île
du Saulcy, 57045 Metz, France. E-mail: [email protected] | KU Leuven, Dep. of Electrical Engineering, Kasteelpark
Arenberg 10, 3001 Leuven, Belgium.
E-mail: [email protected]
Abstract: In a previous paper we formulated and analyzed the structure of
neighborhoods of cellular automata in an algebraic setting such that the
cellular space S is represented by the Cayley graph of a finitely generated
group and the neighbors are defined as a semigroup generated by the
neighborhood N as a subset of S, Nishio and Margenstern 2004 [14,15].
Particularly we discussed the horse power problem whether the motion of a horse
(knight) fills the infinite chess board or Z^2 – that is, an
algebraic problem whether a subset of a group generates it or not. Among others
we proved that a horse fills Z^2 even when its move is restricted to properly
chosen 3 directions and gave a necessary and sufficient condition for a
generalized 3-horse to fill Z^2. This paper gives further developments of the
horse power problem, say, on the higher dimensional Euclidean grid, the
hexagonal grid and the hyperbolic plane.
