Information Dynamics of Cellular Automata I -An Algebraic Study

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

Abstrakty

EN

Information dynamics of cellular automata(CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate X called information variable and its dynamics is investigated by extending CA to CA[X] whose cell states are polynomials in X. For the global configuration of extended CA[X], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[X] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in the separate sections. Decision problems are also referred.

Słowa kluczowe

EN

cellular automata; polynomials over finite fields; dynamical system; completeness; degeneracy; reversibility

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 399--420
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Nishio H.

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

autor

Saito T.

• Faculty of Information Science and Technology, Osaka Institute of Technology, Osaka 573-0196, Japan

Bibliografia

• [1] Bergman, C., Slutzki, G.: Computational Complexity of Generators and Nongenerators in Algebra, International Journal of Algebra and Computation, 12, 2002, 719-735.
• [2] D’amico, M., Manzini, G., Margara, L.: On computing the entropy of cellular automata, TCS, 290, 2003, 1629-1646.
• [3] Fisher, P. C.: Generation of primes by one-dimensional iterative array, Journal of the ACM, 12, 1965, 388-394.
• [4] Garzon, M.: Models of Massive Parallelism, Analysis of Cellular Automata and Neural Networks, Springer, 1995.
• [5] Goles, E., Martinez, S., Eds.: Cellular Automata and Complex Systems, Kluwer Academic Publishers, 1999.
• [6] Gruska, J.: Foundations of computing, International Thompson Computer Press, 1997.
• [7] Kari, J.: Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science, 127, 1994, 229-254.
• [8] Kolmogorov, A. N.: Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1, 1965, 1-7.
• [9] Lidl, R., Niederreiter, H.: Finite Fields, Second edition, Cambridge University Press, 1997.
• [10] Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata, TCS, 217, 1999, 53-80.
• [11] Nishio, H.: Algebraic studies of information in cellular automata, Technical Report 1109, RIMS, Kyoto University, 1999.
• [12] Nishio, H.: An algebraic study of information in cellular automata, Technical Report 2000-22, University of Karlsruhe, 2000, ACRI2000 Work in progress presentation.
• [13] Nishio, H.: Cellular automata with polynomials over finite fields, Proc. 3rd International Colloquium on Words, Languages and Combinatorics (M. Ito, T. Imaoka, Eds.), World Scientific, 2003.
• [14] Nishio, H., Saito, Т.: Information Dynamics of Cellular Automata: Informational Completeness and Reversibility, 2001, Manuscript for 7th IFIP 1.5 Conference, Giens, France.
• [15] Nishio, H., Saito, Т.: Information Dynamics of Cellular Automata II: Completeness, Degeneracy and Entropy, 2002, Manuscript for 8th IFIP 1.5 Conference, Prague, Chech.
• [16] Shannon, C. E.: The mathematical theory of communication. Bell System Technical J, 27, 1948, 379-423, 623-659.
• [17] Smith III, A. R.: Real-time language recognition by one-dimensional cellular automata. Journal of the ACM, 6, 1972, 233-253.
• [18] Takahashi, H.: Information transmission in one-dimensional cellular space and the maximum invariant set, Information and Control, 33, 1977, 35-55.
• [191 von Neumann, J., Burks, A. (ed.): Theory of Self-reproducing Automata, Univ. of Illinois Press. 1966.
• [20] Waksman, A.: An optimal solution to the firing squad synchronization problem. Information and control 8, 1966, 66-78.
• [21] Worsch, Т.: private communication. October 2001.
• [22] Worsch, Т.: slides for talk; http://www.ira.uka.de/ worsch/talks/me tz2002.pdf, 2002.