Automorphism Classification of Cellular Automata

• Autorzy: Nishio, H.
• Języki publikacji: EN

Abstrakty

EN

A new classification of arbitrary cellular automata (CA for short) in Z^d is studied considering the set (group) of all permutations of the neighborhood v and state set Q. Two CA (Z^d, Q, f_A, .A) and (Z^d, Q, f_B, v_B) are called automorphic, if there is a pair of permutationsπ&pfi" of v and Q, respectively, such that (f_B, vB) = ([formula] where v^π denotes a permutation of v and f*π denotes a permutation of arguments of local function f corresponding to v*π This automorphism naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1- dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes.

Słowa kluczowe

EN

cellular automation; automorphism; classification; permutations; neighborhood; group action; ECA

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 125-140
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Nishio, H.

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

Bibliografia

• [1] Buchholz, T., Kutrib, M.: On time computability of functions in one-way cellular automata, Acta Informaticae, 35, 1998, 329-352.
• [2] Cameron, P. J.: Permutation Groups, Series: London Math. Soc. Student Texts No. 45, Cambridge University Press, 1999.
• [3] Chua, L., Sbitnev, V., Yoon, S.: A nonlinear dynmics perspective of Wolfram's new kind of science. Part III: Predicting the unpredictable, Int. Journal of Bifurcation and Chaos, 14, 2004, 3689-3820.
• [4] Gardner, M.: The fantastic combinations of John Conway's new game of 'life', Scientific American, 223, 1970, 120-123.
• [5] Garzon, M.: Models of Massive Parallelism, Analysis of Cellular Automata and Neural Networks, Springer, 1995.
• [6] Guan, J., Shen, S., Tang, C., Chen, F.: Extending Chua's global equivalence theorem on Wolfram's New Kind of Science, Int. Journal of Bifurcation and Chaos, 17, 2007, 4245 - 4259.
• [7] Harrison, M. A.: The Number of Transitivity sets of Boolean Functions, J. Soc. Indust. Appl. Math., 11, 1963, 806-828.
• [8] Lidl, R., Niederreiter, H.: Finite Fields, Second edition, Cambridge University Press, 1997.
• [9] Lode, C.: http://www.clawsoftware.com/projects/catest/.
• [10] Nishio, H.: Changing the Neighborhood of Cellular Automata, Proceedings of MCU2007, eds. J. Durand-Lose and M. Margenstern, LNCS 4664, 2007.
• [11] Nishio, H.: AUTOMORPHISM CLASSIFICATION OF CELLULAR AUTOMATA, Proceedings of Workshop on Non-Classical Models for Automata and Applications(NCMA), [e-mail], 2009.
• [12] Nishio, H., Saito, T.: Information Dynamics of Cellular Automata I: An Algebraic Study, Fundamenta Informaticae, 58, 2003, 399-420.
• [13] Nishio, H., Worsch, T.: Local Strucure of Cellular Automata., k^oky^uroku vol. 1599 (2008) 17-23, RIMS, Kyoto University.
• [14] Nishio, H., Worsch, T.: Changing the neighborhood of cellular automata : local structure, equivalence and isomorphism., J. Cellular Automata, 5(3), 2010, 227-240.
• [15] Pólya, G., Read, R. C.: Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987.
• [16] Roka, Z.: Simulations between cellular automtata on Cayley graphs, Theoretical Computer Science, 225, 1999, 81-111.
• [17] Scheben, C.: http://www.stud.uni-karlsruhe.de/ uoz3/cgi/main.cgi/menu=submenuPrograms&view=view/ca.html.
• [18] Slepian, D.: On the number of symmetry types of Boolean functions of n variables, Canadian J. Math., 5, 1953, 185-193.
• [19] Terrier, V.: Two dimensional cellular automata and their neighborhoods, TCS, 312, 2004, 203-222.
• [20] von Neumann, J., Burks(ed.), A. W.: Theory of Self-reproducing Automata, Univ. of Illinois Press, 1966.
• [21] Wolfram, S.: Cellular Automata and Complexity, Addison-Wesley, 1994.
• [22] Worsch, T., Nishio, H.: Achieving universality of CA by changing the neighborhood, J. Cellular Automata, 4(3), 2009, 237-246.