References

1

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

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

15

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

16

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

17

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

18

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.

19

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

20

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

21

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

22

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).

23

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

24

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

25

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

26

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

27

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

28

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.

29

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

30

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

31

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

32

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

33

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

34

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

35

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).

36

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

37

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

38

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

39

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

40

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

41

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

42

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

43

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

44

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

45

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

46

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

47

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

48

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