On Algebraic Structure of Neighborhoods of Cellular Automata-Horse Power Problem-

• Autorzy: Nishio H. , Margenstern M. , Haeseler F. von
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cellular automata; neighbourhood; horse power problem; finitely generated group; semigroup; hexagonal grid; hyperbolic plane

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 3
• Strony: 397--416
• Opis fizyczny: bibliogr. 17 poz., rys.

Twórcy

autor

Nishio H.

autor

Margenstern M.

autor

Haeseler F. von

• Iwakura Miyake-cho 204, Sakyo-ku, 606-0022 Kyoto, Japan,

Bibliografia

• [1] Babai, L.: The growth rate of vertex-transitive planer graphs, 8th Annual ACM-SIAMSymposium on Discrete Algorithms, 1997.
• [2] Bergman, C., Slutzki, G.: Computational Complexity of Generators and Nongenerators in Algebra, International Journal of Algebra and Computation, 12, 2002, 719-735.
• [3] Bollobas, B.: Graph Theory, Springer-Verlag, 1979.
• [4] Burris, S., Sankappanavar, H. P.: A Course in Universal Algebra, The millennium edition, Open website, 2000.
• [5] Chang, J., Ibarra, O., Vergis, A.: On the power of one-way communication, ACM, 35, 1988, 697-726.
• [6] Codd, E. F.: Cellular Automata, Academic Press, 1968.
• [7] Klein, A., Kutrib, M.: Fast one-way cellular automata, TCS, 295, 2003, 233-250.
• [8] Machi, A., Mignosi, F.: Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups, SIAM J. Disc. Math., 6, 1993, 44-56.
• [9] M. Margenstern, New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science, 6, N_12, (2000), 1226-1252.
• [10] M. Margenstern, Tiling the hyperbolic plane with a single pentagonal tile, Journal of Universal Computer Science, 8, N_2, (2002), 297-316.
• [11] M. Margenstern, K. Morita, NP problems are tractable in the space of cellular automata in the hyperbolic plane, Theoretical Computer Science, 259, (2001), 99-128.
• [12] Markov, A. A.: On the impossibility of certain algorithms in the theory of associative systems, Dokl. Acad. Nauk. USSR (English translation), 55, 1947, 583-586.
• [13] Newman, M.: Integral Matrices, Academic Press, 1972.
• [14] Nishio, H., Margenstern, M.: An algebraic Analysis of Neighborhoods of Cellular Automata, Submitted to J.UCS, 2004.
• [15] Nishio, H., Margenstern, M.: An algebraic Analysis of Neighborhoods of Cellular Automata, Technical Report (kokyuroku) vol. 1375, RIMS, Kyoto University, May 2004, Proceedings of LA Symposium, Feb. 2004.
• [16] Roka, Z.: One-way cellular automata on Cayley graphs, Theoretical Computer Science, 132, 1994, 259-290.
• [17] Terrier, V.: Cellular automata recognizer with restricted communication, Technical Report 32, Turku Center for Computer Science, June 2004, Proceedings of DMCS'04.