Revisão Bibliográfica: Autômatos Celulares

Parallel Computing

pp. 539-553

Authors: Bandini, S.a; Mauri, G.a; Serra, R.b

Affiliations: a. Department of Computer Science, Systems and Communication (DISCo),

University of Milano-Bicocca, Via Bicocca degli Arcimboldi, 8-20134, Milan, Italy

b. Centro Ricerche Ambientali Montecatini, Via Ciro Menotti, 48-48023, Marina

di Ravenna, Italy

Keywords: Cellular automata; Applications; Complex systems

Abstract:

This introductory paper gives a short survey of cellular automata (CAs), from different points of view. It starts with the main definitions and theoretical results about CAs as an abstract model of computation or as discrete dynamical systems. Then, the main applications of CAs in different fields (biology, physics, etc.) as a model of complex systems are illustrated. Finally, implementations of the CA model on parallel computing platforms are surveyed.

Publisher: Elsevier Science

Language of Publication: English

Item Identifier: S0167-8191(00)00076-4

Publication Type: Article

ISSN: 0167-8191

Citations:

1.Adorni, G., Cellular Automata: Research Towards Industry 1998

2.H. Arata, Y. Takai, N.K. Takai, T. Yamamoto, Free-form shape modeling

by 3D cellular automata, in: Proceedings of Shape Modeling

International'99, 1999

3.D.E. Atkinson, M.C. Sawada, K. Gajewski, Emergent spatial structure in

vegetation succession, in: Proceedings of the Annual Meeting of the

Canadian Association of Geographer, Ottawa, 1998

4.Bak, P., "Self-organized criticality" Phys. Rev. A 1988 pp. 364-374

5.P. Bak, How nature works: The Science of Self-organized Criticality,

Copernicus Books, 1996

6.Baltzer, H., "Cellular automata models for vegetation dynamics" Ecol.

Modeling 1998 pp. 113-125

7.Bandini, S., "Multilayered automata networks" Theoret. Comput. Sci.

1999 pp. 99-113 Bibliographic Page Full Text

8.S. Bandini, G. Erbacci, G. Mauri, Implementing cellular automata based

models on parallel architectures: The CAPP project, in: V. Malyshkin

(Ed.), Parallel Computing Technologies, Lecture Notes in Computer

Science, vol. 1662, Springer, Berlin, 1999

9.S. Bandini, G. Mauri, G. Pavesi, C. Simone, Parallel simulation of

reaction–diffusion phenomena in percolation processes: A model based

on cellular automata, in: Future Generation Computer Systems, Elsevier,

Amsterdam, 2000a

10.S. Bandini, M. Magagnini, Parallel processing simulation of dynamic

properties of filled rubber compounds based on cellular automata,

Parallel Computing 27 (2001), this issue

11.E.R. Banks, Information processing and transmission in cellular

automata, MIT Project, MAC Report No. TR-81, 1971

12.M. Batty, H. Couclelis, M. Eichen (Eds.), Urban Systems as Cellular

Automata (special issue), Planning Design 24 (2) (1997)

13.E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways, vol. 2,

Academic Press, 1985 (Chapter 25)

14.Boccara, N., Cellular Automata, Dynamical Systems and Neural

Networks 1994

15.Braga, G., "Pattern growth in elementary cellular automata" Theoret.

Comput. Sci. 1995 pp. 1-26

16.Burks, E., Theory of Self-Reproduction 1966

17.Burks, A.W., Essays on Cellular Automata 1970

18.Burks, E., Essays on Cellular Automata 1972

19.Cannataro, M., "A parallel cellular automata environment on

multicomputers for computational science" Parallel Comput. 1995 pp.

803-824

20.R. Cappuccio, G. Cattaneo, G. Erbacci, U. Jocher, A parallel

implementation of a cellular automata based model for coffee percolation,

Parallel Computing 27 (2001), this issue

21.G. Cattaneo, E. Formenti, L. Margara, Topological definitions of

deterministic chaos, in: J. Mazoyer (Ed.), Cellular Automata, Kluwer

Academic Publishers, Dordrecht, 1999

22.Celada, F., "A computer model of cellular interactions in the immune

system" Immunol. Today 1992 pp. 56-62

23.Chopard, B., Cellular Automata Modeling of Physical Systems 1998

24.Codd, E.F., Cellular Automata 1968

25.Colasanti, R.L., "Resource dynamics and vegetation processes, a

deterministic model using two-dimensional cellular automata" Functional

Ecol. 1993 pp. 169-176

26.J.H. Conway, Unpublished, quoted in [13]

27.Crutchfield, J.P., "The evolution of emergent computation" Proc. Natl.

Acad. Sci., USA 1995 pp. 10742-10746

28.Culik II, K., "Undecidability of CA classification schemes" Complex

Systems 1988 pp. 177-190

29.Culik II, K., "On the limit sets of cellular automata" SIAM J. Comput.

1989 pp. 831-842

30.Cellular Automata 1999

31.Di Gregorio, S., "A cellular automata model of soil bioremediation"

Complex Systems 1997 pp. 31-54

32.Di Gregorio, S., "An empirical method for modelling and simulating some

complex phenomena by cellular automata" Future Generation Comput.

Systems 1999 pp. 259-271

33.Di Gregorio, S., "Applying cellular automata to complex environmental

problems: The simulation of the bioremediation of contaminated soils"

Theoret. Comput. Sci. 1999 pp. 131-156 Bibliographic Page Full Text

34.Epstein, J.M., Growing Artificial Societies: Social Science from the

bottom up 1996

35.Ginsberg, A., Cellular Automata: Research Towards Industry 1998

36.Goles, E., Neural and Automata Networks: Dynamical Behavior and

Applications 1990

37.Green, D.G., Plants to Ecosystem 1997

38.Hardy, J., "Molecular dynamics of a classic lattice gas: Transport

properties and time correlation functions" Phys. Rev. A 1976 pp.

1949-1960

39.Hedlund, G.A., "Endomorphisms and automorphisms of the shift

dynamical system" Math. System Theory 1969 pp. 320-375

40.T.L. Kunii, Y. Takai, Cellular self-reproducing automata as a parallel

processing model for botanical colony growth pattern simulation, in: New

Advances in Computer Graphics, Springer, Berlin, 1989

41.Kauffman, S.A., The Origins of Order 1993

42.Kauffman, S.A., At Home in the Universe 1995

43.Langton, C.G., "Computation at the edge of chaos: Phase transitions

and emergent computation" Physica D 1990 pp. 12-37

44.Langton, C.G., Artificial Life 1989

45.Artificial Life II 1992

46.Lind, D.A., "Applications of ergodic theory and sofic systems to cellular

automata" Physica D 1984 pp. 36-44

47.Lindgren, K., "Complexity measures and cellular automata" Complex

Systems 1988 pp. 409-440

48.A. Lomi, E.R. Larsen, Interacting locally and evolving globally: A

computational approach to the dynamics of organizational populations,

Acad. Manage. J. (39) (1996)

49.Marques Pereira, R.A., Complexity in Physics and Technology 1992

50.Milnor, J., "On the entropy geometry of cellular automata" Complex

Systems 1988 pp. 257-385

51.Mitchell, M., "Revisiting the edge of chaos: Evolving cellular automata to

perform computation" Complex Systems 1993 pp. 89-130

52.Moore, E.F., "Machine models of self-reproduction" Proc. Symp. Appl.

Math. 1962 pp. 17-33

53.Myhill, J., "The converse of Moore's garden-of-eden theorem" Proc. AMS

1963 pp. 685-686

54.Packard, N.H., Dynamic Patterns in Complex Systems 1988

55.Resnick, M., Turtles, Termites and Traffic Jams 1994

56.Richardson, D., "Tessellations with local transformations" J. Comput.

System Sci. 1972 pp. 373-388

57.Serra, R., "Modelling bacterial degradation of organic compounds with

genetic networks" J. Theoret. Biol. 1997 pp. 107-119

58.Serra, R., Biotechnology for Soil Remediation 1998

59.R. Serra, M. Villani, A. Salvemini, Continuous genetic networks, Parallel

Computing 27 (2001), this issue

60.R. Serra, M. Villani, A. Colacci, A cellular automata model for the

simulation of in vitro carcinogenesis tests, in: T. Worsch, S. Bandini

(Eds.), Proceedings of ACRI 2000, Springer, London, 2000

61.K. Satoh, Computer experiment on the complex behavior of a

two-dimensional cellular automaton as a phenomenological model for an

ecosystem, J. Phys. Soc. Jpn. (58) (1989)

62.Smith, A.R., "Simple computation-universal cellular spaces" J. ACM

1971 pp. 339-353

63.Traffic and Granular Flow'97 1998

64.Succi, S., "The lattice Boltzmann equation: A new tool for computational

fluid dynamics" Physica D 1991 pp. 219-230

65.Takai, Y., "A cellular automaton model of particle motions and its

applications" The Visual Comput. 1995

66.Y. Takai, N.K. Takai, K.J. Nakamori, Exploration of the reaction–diffusion

textures, in: Proceedings of the International Conference on Modelling

and Simulation, 1998

67.D. Talia, Parallel cellular automata for high performance computational

simulation, in: Proceedings of HPC'98, SCS Press, San Diego, 1998

68.J. Thatcher, Universality in the von Neumann cellular model, Technical

Report 03105-30-T, University of Michigan, 1964

69.W. Tobler, Mathematical map models, in: Proc. Int. Symposium on

Computer Aided Cartography, Reston, American Congress on Surveying

and Mapping, 1975, pp. 66–73

70.Toffoli, T., Cellular Automata Machines 1987

71.Villani, M., Theoretical and Practical Issues on Cellular Automata 2000

72.von Neumann, J., Theory of Self-reproducing Automata 1966

73.Wolfram, S., Theory and Applications of Cellular Automata 1986

74.Wolfram, S., Cellular Automata and Complexity 1994

75.T. Worsch, Programming environments for cellular automata, in: S.

Bandini, G. Mauri (Eds.), Proceedings of ACRI'96, Springer, London,

1996

Fonte: www.ifs.tuwien.ac.at/~aschatt/info/ca/ca.html