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).
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx