References

1

Milton Abramowitz and Irene A. Stegun (Editors), Handbook of Mathematical Functions, U. S. Government Printing Office, Washington D. C., 1964.

2

Roy Adler and Leopold Flatto, ``Geodesic Flows, Interval Maps, and Symbolic Dynamics,'' Bulletin of the American Mathematical Society 25 229-334 (1991).

3

Jürgen Albert and Karel Culik II, ``A Simple Universal Cellular Automaton and its One-Way and Totalistic Version,'' Complex Systems 1 1-16 (1987).

4

S. Amoroso and Y. N. Patt, ``Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tesselation Structures,'' Journal of Computer and System Sciences 6 448-464 (1972).

5

R. C. Backhouse and B. A. Carré, ``Regular Algebra Applied to Path-finding Problems,'' Journal of the Institute for Mathematics and its Applications 15 161-186 (1975).

6

Carter Bays, ``The game of three dimensional life'' (11/20/86) unpublished (available as a supplement to A. K. Dewdney's February 1987 column).

7

Carter Bays, ``Candidates for the Game of Life in Three Dimensions,'' Complex Systems 1 373-400 (1987).

8

Carter Bays, ``Patterns for Simple Cellular Automata in a Universe of Dense-Packed Spheres,'' Complex Systems 1 853-875 (1987).

9

Carter Bays, ``Classification of Semitotalistic Cellular Automata in Three Dimensions,'' Complex Systems 1 373-400 (1987).

10

Richard Bellman, Introduction to Matrix Analysis, McGraw-Hill Book Company, New York, 1960.

11

I. S. Berezin and N. P. Zhidkov, Computing Methods, volume 1, Pergamon Press, Oxford, 1965.

12

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your Mathematical Plays, Academic Press, 1982 (ISBN 0-12-091152-3) vol. 2, chapter 25.

13

Abraham Berman and Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979 (ISBN 0-12-092250-9).

14

R. Bidaux, N. Boccara, and H. Chaté, ``Order of the transition versus space dimension in a family of cellular automata,'' Physical Review A 39 3094-3105 (1989).

15

George D. Birkhoff, Dynamical Systems, American Mathematical Society, Providence, Rhode Island, 1927.

16

David B. Brown, ``Competition of cellular automata rules,'' Complex Systems 1 169-180 (1987).

17

Janusz A. Brzozowski, ``Derivatives of regular expressions,'' Journal of the Association for Computing Machinery 11 481-494 (1964).

18

David J. Buckingham, ``Some facts of life,'' Byte vol. 3, no. 12 (December, 1978), pp. 54-67.

19

Arthur W. Burks (editor), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970.

20

Noam Chomsky, ``Three models for the description of language,'' IRE Transactions on Information Theory bf IT-2 113-124 (1956).

21

Noam Chomsky and George A. Miller, ``Finite state languages,'' Information and Control bf 1 91-112 (1958).

22

Noam Chomsky, ``On certain formal properties of grammars,'' Information and Control bf 1 137-167 (1958).

23

Noam Chomsky, ``Formal properties of grammars,'' in Handbook of Mathematical Psychology, volume 2, John Wiley and Sons, New York, 1963, pp. 323-418.

24

Gerardo Cisneros and Harold V. McIntosh, Notas sobre los lenguajes REC y Convert (Spanish), Universidad Autonoma de Puebla, 1986.

25

E. F. Codd, Cellular Automata, Academic Press, New York, 1968.

26

J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, Ltd., London, 1971 (ISBN 412-10620-5).

27

P-. J, Courtois and P. Semal, ``Bounds for the Positive Eigenvectors of Nonnegative Matrices and for their Approximations by Decomposition,'' Journal of the Association for Computing Machinery 31 804-825 (1984).

28

Karel Culick II, ``On Invertible Cellular Automata,'' Complex Systems 1 1036-1044 (1987).

29

Karel Culick II and Sheng Yu, ``Undecidability of CA Classification Schemes,'' Complex Systems 2 177-190 (1988).

30

Karel Culick II, Jan Pachl, and Sheng Yu, ``On the Limit Sets of Cellular Automata,'' SIAM Journal on Computing 18 831-842 (1989).

31

Predrag Cvitanovic, ``Invariant measurement of strange sets in terms of cycles,'' Physical Review Letters 24 2729-2732 (1988).

32

A. K. Dewdney, ``Computer Recreations - Building computers in one dimension sheds light on irreducibly complicated phenomena,'' Scientific American, May 1985, pp. 10-16.

33

A. K. Dewdney, ``Computer Recreations - The game Life acquires some successors in three dimensions,'' Scientific American, February 1987, pp 8-13.

34

A. K. Dewdney, The Armchair Universe, W. H. Freeman and Company, New York, 1988. (ISBN 0-7167-1939-8 pbk)

35

M. Dresden and D. Wong, ``Life Games and Statistical Models,'' Proceedings of the National Academy of Sciences (U.S.A.) 72 956-960 (1975).

36

Michel Dubois-Violette and Alain Rouet, ``A Mathematical Classification of the One-Dimensional Deterministic Cellular Automata,'' Communications in Mathematical Physics 112 627-631 (1987), ``Addendum,'' 118 529 (1988).

37

Manfred Eigen, ``Abstract: The Hypercycle: A Principle of Natural Self-Organization,'' International Journal of Quantum Chemistry, Quantum Biology Symposium 5 219 (1978).

38

Samuel Eilenberg, Automata, Languages, and Machines, Volume A, Academic Press, New York, 1974. (ISBN 0-12-234001-9 (pt. A.))

39

Samuel Eilenberg, Automata, Languages, and Machines, Volume B, Academic Press, New York, 1976. (ISBN 0-12-234002-7 (pt. B.))

40

William Feller, An Introduction to Probability Theory and its Applications, volume 2 (second edition), John Wiley and Sons, New York.

41

F. R. Gantmacher, The Theory of Matrices, volume 2, Chelsea Publishing Company, New York, 1959.

42

Martin Gardner, ``Mathematical Games - The fantastic combinations of John Conway's new solitaire game Life, '' Scientific American, October 1970, pp. 120-123.

43

Martin Gardner, Wheels, Life, and Other Mathematical Amusements, W. H. Freeman and Company, New York, 1983. (ISBN 0-7167-1589-9 pbk)

44

Solomon W. Golomb, Shift Register Sequences, Holden-Day, Inc., San Francisco, 1967.

45

Walter Helbig Gottschalk and Gustav Arnold Hedlund, Topological Dynamics, American Mathematical Society, Providence, Rhode Island, 1955.

46

J. M. Greenberg and S. P. Hastings, ``Spatial patterns for discrete models of diffusion in excitable media,'' SIAM Journal on Applied Mathematics 34 515-523 (1978).

47

J. M. Greenberg, B. D. Hassard, and S. P. Hastings, ``Pattern formation and periodic structures in systems modelled by reaction-diffusion equations,'' Bulletin of the American Mathematical Society 84 1296-1327 (1978).

48

J. M. Greenberg, C. Greene, and S. Hastings, ``A combinatorial problem arising in the study of reaction-diffusion equations,'' SIAM Journal of Algebra and Discrete Mathematics 1 34-42 (1980).

49

P. Guan and Y. He, ``Upper bound on the number of cycles in border-decisive cellular automata,'' Complex Systems 1 181-186 (1987).

50

Howard A. Gutowitz and Jonathan D. Victor, ``Local structure theory in more than one dimension,'' Complex Systems 1 57-68 (1987).

51

Howard A. Gutowitz, Jonathan D. Victor, and Bruce W. Knight, ``Local structure theory for cellular automata,'' Physica 28D 18-48 (1987).

52

Howard A. Gutowitz and Jonathan D. Victor, "Local structure theory: calculation on hexagonal arrays, and interaction of rule and lattice," Journal of Statistical Physics 54 495-514 (1989).

53

Fred Hapgood, ``Let there be Life,'' Omni, vol. 9, no. 7 (April 1987) pp. 40-46, 116-117.

54

Brian Hayes, ``Computer Recreations - The cellular automaton offers a model of the world and a world unto itself,'' Scientific American, March 1984, pp. 10-16.

55

Tom Head, ``One-Dimensional Cellular Automata: Injectivity from Unambiguity,'' Complex Systems 3 343-348 (1989).

56

G. A. Hedlund, ``Endomorphisms and automorphisms of the shift dynamical system,'' Mathematical Systems Theory 3 320-375 (1969).

57

J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Massachusetts, 1979.

58

Lyman P. Hurd, ``Formal Language Characterizations of Cellular Automaton Limit Sets,'' Complex Systems 1 69-80 (1987).

59

Lyman P. Hurd, ``The Non-wandering Set of a CA Map,'' Complex Systems 2 549-554 (1988).

60

Oscar H. Ibarra and Tao Jiang, ``On one-way cellular arrays,'' SIAM Journal on Computing 16 1135-1154 (1987).

61

Hiroyuki Ito, ``Intriguing properties of global structure in some classes of finite cellular automata,'' Physica D 31 318-338 (1988).

62

Erica Jen, ``Scaling of preimages in cellular automata,'' Complex Systems 1 1045-1062 (1987).

63

Erica Jen, ``Cylindrical Cellular Automata,'' Communications in Mathematical Physics 118 569-590 (1988).

64

Kunehiko Kaneko, ``Attractors, basin structures and information processing in cellular automata'' in Theory and Applications of Cellular Automata (Stephen Wolfram, ed.), World Scientific, Singapore, 1986. pp. 367-399.

65

Youichi Kobuchi and Hidenosuki Nishio, ``Some regular state sets in the system of one-dimensional iterative automata,'' Information Sciences 5 199-216 (1973).

66

Zvi Kohavi, Switching and Finite Automata Theory (second edition), McGraw-Hill Book Company, New York, 1978 (ISBN 0-07-035310-7).

67

A. N. Kolmogorov, Foundations of the Theory of Probability, Chelsea Publishing Company, New York, 1950.

68

K. B. Krohn and J. L. Rhodes, ``Algebraic Theory of Machines,'' Mathematical Theory of Automata, Polytechnic Press, Brooklyn, New York, 1963. pp. 341-384.

69

Christopher G. Langton, ``Self-reproduction in cellular automata'' Physica D 10 135-144 (1984).

70

Christopher G. Langton, ``Studying artificial life with cellular automata,'' Physica D 22 120-149 (1986).

71

Christopher G. Langton, ``Computation at the edge of chaos: phase transitions and emergent computation,'' Physica D 42 12-47 (1990).

72

Stephen Levy, Hackers: Heroes of the Computer Revolution, Anchor Press/ Doubleday, Garden City, New York, 1984 (ISBN 0-385-19195-2), chapter 7.

73

Wentian Li, ``Power spectra of regular languages and cellular automata,'' Complex Systems 1 107-130 (1987).

74

Wentian Li, Norman Packard, and Christopher G. Langton, ``Transition phenomena in cellular automaton rule space,'' Physics D 45 77-94 (1990).

75

G. G. Lorentz, Bernstein Polynomials, University of Toronto Press, Toronto, 1953.

76

Barry F. Madore and Wendy L. Freedman, ``Computer simulations of the Belousov-Zhabotinsky reaction,'' Science 222 615-616 (1983).

77

O. Martin, A. Odlyzko, and S. Wolfram, ``Algebraic aspects of cellular automata,'' Communications in Mathematical Physics 93 219-258 (1984).

78

Marvin L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, New Jersey, 1967.

79

W. S. McCulloch and W. Pitts, ``A logical calculus of the ideas immanent in nervous activity,'' Bulletin of Mathematical Biophysics 5 115-133 (1943).

80

Henryk Minc, Nonnegative Matrices, John Wiley and Sons, New York, 1988 (ISBN 0-471-83966-3).

81

Edward F. Moore, ``Gedanken Experiments on Sequential Machines,'' in C. E. Shannon and John McCarthy (eds), Automata Studies, Princeton University Press, Princeton, New Jersey, 1956.

82

Edward F. Moore, ``Machine models of self reproduction,'' American Mathematical Society Proceedings of Symposia in Applied Mathematics 14 17-33 (1962).

83

Edward F. Moore, ``The firing squad synchronization problem,'' in Edward F. Moore (ed), Sequential Machines: Selected Papers, Addison-Wesley, Reading, Massachusetts, 1964. pp. 213-214.

84

Edward F. Moore, ``Machine models of self-reproduction,'' in A. Burks (ed), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970.

85

Scott Morris, ``Games - The game of Life,'' Omni, vol. 7, no. 1 (October, 1984), pp. 188-189.

86

Masakazu Nasu, ``Local Maps Inducing Surjective Global Maps of One Dimensional Tessellation Automata,'' Mathematical Systems Theory 11 327-351 (1978).

87

Masakazu Nasu, ``Indecomposable Local Maps of Tesselation Automata,'' Mathematical Systems Theory 13 81-93 (1979).

88

Masakazu Nasu, ``An Interconnection of Local Maps Inducing Onto Global Maps,'' Discrete Applied Mathematics 2 125-150 (1980).

89

Masakazu Nasu, ``Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs,'' Discrete Mathematics 39 171-197 (1982).

90

John von Neumann, Theory of Self-reproducing Automata (edited and completed by A. W. Burks), University of Illinois Press, 1966.

91

Mark D. Niemiec, ``Life Algorithms,'' Byte vol. 4, no 1 (January, 1979) pp. 90-97.

92

Norman H. Packard and Stephen Wolfram, ``Two-Dimensional Cellular Automata,'' Journal of Statistical Physics 38 901-946 (1985).

93

Asher Peres, ``Reversible logic and quantum computers,'' Physical Review A 32 3266-3276 (1985).

94

M. Perles, M. O. Rabin, and E. Shamir, ``The Theory of Definite Automata,'' IEEE Transactions on Electronic Computers EC-12 233-243 (1963).

95

Kenneth E. Perry, ``Abstract mathematical art,'' Byte, vol. 11, no. 13 (December 1986), pp. 181-192.

96

William Poundstone, The Recursive Universe, William Morrow and Company, New York, 1985 (ISBN 0-688-03975-8).

97

Kendall Preston, Jr., and Michael J. B. Duff, Modern Cellular Automata, Plenum Press, New York, 1984 (ISBN 0-306-41737-5).

98

Anthony Ralston, ``De Bruijn Sequences---A Model Example of the Interaction of Discrete Mathematics and Computer Science,'' Mathematics Magazine 55 131-143 (1982).

99

D. Richardson, ``Tessellations with local transformations,'' Journal of Computer and System Sciences 6 373-388 (1972).

100

D. R. Rutherford, Substitutional Analysis, Edinburgh, at the University Press (1948).

101

Tadakazu Sato and Namio Honda, ``Certain Relations between Properties of Maps of Tesselation Automata,'' Journal of Computer and System Sciences 15 121-145 (1977).

102

L. S. Schulman and P. E. Seiden, ``Statistical mechanics of a dynamical system based on Conway's game of Life,'' Journal of Statistical Physics 19 293-314 (1978).

103

Eugene Seneta, Non-Negative Matrices, John Wiley and Sons, New York, 1973 (ISBN 0-470-77605-6).

104

Claude E. Shannon and John McCarthy (editors), Automata Studies, Annals of Mathematics Studies #34, Princeton University Press, Princeton, 1956. (ISBN 0-691-07916-1).

105

J. A. Shohat and J. D. Tamarkin, The Problem of Moments, American Mathematical Society, Providence, Rhode Island, 1943.

106

Sven Skyum, ``Confusion in the Garden of Eden,'' Proceedings of the American Mathematical Society 50 332-336 (1975).

107

Alvy Ray Smith III, ``Simple computation-universal cellular spaces,'' Journal of the Association for Computing Machinery 18 339-353 (1971).

108

Shinji Takesue, ``Reversible Cellular Automata and Statistical Mechanics,'' Physical Review Letters 59 2499-2502 (1987).

109

Tommaso Toffoli, ``Computation and Construction Universality of Reversible Cellular Automata,'' Journal of Computer and System Sciences 15 213-231 (1977).

110

Tommaso Toffoli and Norman Margolus, Cellular Automata Machines, The MIT Press, Cambridge, Massachusetts, 1987. (ISBN 0-262-20060-0).

111

Stanislaw Ulam, ``On some mathematical problems connected with patterns of growth of figures,'' in A. Burks (ed.) Essays on Cellular Automata, University of Illinois Press, 1970.

112

Richard S. Varga, Matrix Iterative Analysis, Prentice Hall, Inc, Englewood Cliffs, New Jersey, (1962).

113

Robert T. Wainwright (editor), Lifeline, a quarterly newsletter with 11 issues published between March 1971 and September 1973.

114

A. Waksman, ``An optimum solution to the firing squad synchronization problem,'' Information and Control 9 66-78 (1966).

115

Norbert Wiener, Cybernetics, John Wiley and Company, New York, (1948).

116

W. John Wilbur, David J. Lipman, and Shihab A. Shamma, ``On the prediction of local patterns in cellular automata,'' Physica 19D 397-410 (1986).

117

Stephen J. Willson, ``Growth rates and fractional dimensions in cellular automata,'' Physica 10D 69-74 (1984).

118

Stephen Wolfram, ``Statistical mechanics of cellular automata,'' Reviews of Modern Physics 55 601-644 (1983).

119

Stephen Wolfram, ``Universality and complexity in cellular automata,'' Physica 10D 1-35 (1984).

120

Stephen Wolfram, ``Computation theory of cellular automata,'' Communications in Mathematical Physics 96 15-57 (1984).

121

Stephen Wolfram (Ed.), Theory and Applications of Cellular Automata, World Scientific Press, Singapore, 1986 (ISBN 9971-50-124-4 pbk).

122

Takeo Yaku, ``The constructibility of a configuration in a cellular automaton,'' Journal of Computer and System Sciences 7 481-496 (1973).