References

[1] Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. 55, 601 (1983).

[2] Wolfram, S.: Universality and complexity in cellular automata. Physica 10D, 1 (1984).

[3] Packard, N. H.: Complexity of growing patterns in cellular automata, Institute for Advanced Study preprint (October 1983), and to be published in Dynamical behaviour of automata. Demongeot, J., Goles, E., Tchuente, M., (eds.). Academic Press (proceedings of a workshop held in Marseilles, September 1983).

[4] Wolfram, S.: Cellular automata as models for complexity. Nature (to be published).

[5] Wolfram, S.: Cellular automata. Los Alamos Science, Fall 1983 issue.

[6] Beckman, F. S.: Mathematical foundations of programming. Reading, MA: Addison-Wesley 1980.

[7] Hopcroft, J. E., Ullman, J. D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979.

[8] Minsky, M.: Computation: finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall 1967.

[9] Rozenberg, G., Salomaa, A. (eds.): L systems. In: Lecture Notes in Computer Science, Vol. 15; Rozenberg, G., Salomaa, A.: The mathematical theory of L systems. New York: Academic Press 1980.

[10] Guckenheimer, J., Holmes, P.: Nonlinear oscillations, dynamical systems, and bifurcations of vector fields. Berlin, Heidelberg, New York: Springer 1983.

[11] Walters, P.: An introduction to ergodic theory. Berlin, Heidelberg, New York: Springer 1982.

[12] Weiss, B.: Subshifts of finite type and sofic systems. Monat. Math. 17, 462 (1973); Coven, E. M., Paul, M. E.: Sofic systems. Israel J. Math. 20 165 (1975).

[13] Field, R. D., Wolfram, S.: A QCD model for annihilation. Nucl. Phys. B213, 65 (1983).

[14] Smith, A. R.: Simple computation-universal cellular spaces. J. ACM 18, 331 (1971).

[15] Berlekamp, E. R., Conway, J. H., Guy, R. K.: Winning ways for your mathematical plays. New York: Academic Press, Vol. 2, Chap. 25.

[16] Lind, D.: Applications of ergodic theory and sofic systems to cellular automata. Physica 10D, 36 (1984).

[17] de Bruijn, N. G.: A combinatorial problem. Ned. Akad. Weten. Proc. 49, 758 (1946); Good, I. J.: Normal recurring decimals. J. Lond. Math. Soc. 21, 167 (1946).

[18] Nerode, A.: Linear automaton transformations. Proc. AMS 9, 541 (1958).

[19] Cvetkovic, D., Doob, M., Sachs, H.: Spectra of graphs. New York: Academic Press 1980.

[20] Billingsley, P.: Ergodic theory and information. New York: Wiley 1965.

[21] Chomsky, N., Miller, G. A.: Finite state languages. Inform. Control 1, 91 (1958).

[22] Stewart, I. N., Tall, D. O.: Algebraic number theory. London: Chapman & Hall 1979.

[23] Lind, D. A.: The entropies of topological Markov shifts and a related class of algebraic integers. Ergodic Theory and Dynamical Systems (to be published).

[24] Milnor, J.: Unpublished notes (cited in [2]).

[25] Hedlund, G. A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theor. 3, 320 (1969); Hedlund, G. A.: Transformations commuting with the shift. In: Topological dynamics. Auslander, J., Gottschalk, W. H., (eds.). New York: Benjamin 1968.

[26] Amoroso, S., Patt, Y. N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comp. Sys. Sci. 6, 448 (1972).

[27] Nasu, M.: Local maps inducing surjective global maps of one-dimensional tessellation automata. Math. Syst. Theor. 11, 327 (1978).

[28] Garey, M. R., Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman 1979, Sect. A10.

[29] Martin, O., Odlyzko, A. M., Wolfram, S.: Algebraic properties of cellular automata. Commun. Math. Phys. 93, 219 (1984).

[30] Hedlund, G.: Private communication.

[31] Manning, A.: Axiom A diffeomorphisms have rational zeta functions. Bull. Lond. Math. Soc. 3, 215 (1971); Coven, E., Paul, M.: Finite procedures for sofic systems. Monat. Math. 83, 265 (1977).

[32] Franks, J.: Private communication.

[33] Coven, E.: Private communication.

[34] Hurd, L.: Formal language characterizations of cellular automata limit sets (to be published).

[34] Rosenfeld, A.: Picture languages. New York: Academic Press (1979).

[36] Golze, U.: Differences between 1- and 2-dimensional cell spaces. In: Automata, Languages and Development, Lindenmayer, A., Rozenberg, G. (eds.). Amsterdam: North-Holland 1976; Yaku, T.: The constructibility of a configuration in a cellular automaton. J. Comput. System Sci. 7, 481 (1983).

[37] Grassberger, P.: Private communication.

[38] Grassberger, P.: A new mechanism for deterministic diffusion. Phys. Rev. A, (to be published) Chaos and diffusion in deterministic cellular automata. Physica 10D, 52 (1984).

[39] Hillis, D., Hurd, L.: Private communications.

[40] Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Berlin, Heidelberg, New York: Springer 1978.

[41] Kuich, W.: On the entropy of context-free languages. Inform. Cont. 16, 173 (1970).

[42] Chaitin, G.: Algorithmic information theory. IBM J. Res. Dev. 21, 350 (1977).

[43] Kaminger, F. P.: The non-computability of the channel capacity of context-sensitive languages. Inform. Cont. 17, 175 (1970).

[44] Smith, A. R.: Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6, 233 (1972).

[45] Sommerhalder, R., van Westrhenen, S. C.: Parallel language recognition in constant time by cellular automata. Acta Inform. 19, 397 (1983).

[46] Rogers, H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967.

[47] Bennett, C. H.: On the logical ``depth'' of sequences and their reducibilities to random sequences. Inform. Cont. (to be published).

[48] Conway, J. H.: Regular algebra and finite machines. London: Chapman & Hall 1971.

[49] Shannon, C. E.: Prediction and entropy of printed English. Bell Syst. Tech. J. 30, 50 (1951).

[50] Wolfram, S.: SMP reference manual. Computer Mathematics Group. Los Angeles: Inference Corporation 1983.

[51] Packard, N. H., Wolfram, S.: Two dimensional cellular automata. Institute for Advanced Study preprint, May 1984.

[52] Hopcroft, H.: An n log n algorithm for minimizing states in a finite automaton. In: Proceedings of the International Symposium on the Theory of Machines and Computations. New York: Academic Press 1971.

[53] Hurd, L.: Private communication.

previous  l  next