Skip to main content
Springer Nature Link
Log in

Graph-Rewriting Automata as a Natural Extension of Cellular Automata

  • Chapter
  • First Online:
Adaptive Networks

Part of the book series: Understanding Complex Systems ((UCS))

  • 3270 Accesses

  • 11 Citations

Abstract

We introduce a framework called graph-rewriting automata to model evolution processes of networks. It is a natural extension of cellular automata in the sense that a fixed lattice space of cellular automata is extended to a dynamic graph structure by introducing local graph-rewriting rules. We consider three different constructions of rule sets to show that various network evolution is possible: hand-coding, evolutionary generation, and exhaustive search. Graph-rewriting automata provide a new tool to describe various complex systems and to approach many scientific problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Church, A.: An unsolvable problem of elementary number theory. American Journal of Mathematics 58(2), 345–363 (1936)

    Article  MathSciNet  Google Scholar 

  2. Giavitto, J.-L., Spicher, A.: Topological rewriting and the geometrization of programming. Physica D 237(9), 1302–1314 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  3. Gross, T., Blasius, B.: Adaptive coevolutionary networks: a review. Journal of the Royal Society Interface 5(20), 259–271 (2008)

    Article  Google Scholar 

  4. Gruau, F., Eisenbeis, C., Maignan, L.: The foundation of self-developing blob machines for spacial computing. Physica D 237(9), 1282–1301 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  5. Holland, J. H.: Adaptation in Natural and Artificial Systems. University of Michigan Press (1975)

    Google Scholar 

  6. Ilachinski, A.: Cellular Automata, A Discrete Universe. World Scientific (2001)

    Google Scholar 

  7. Ilachinski, A., Halpern, P.: Structurally dynamic cellular automata. Complex Systems 1(3), 503–527 (1987)

    MATH  MathSciNet  Google Scholar 

  8. Kataoka, N.: Modified graph automata. In: Workshop Proc. of ALIFE IX, pp. 137–141 (2006)

    Google Scholar 

  9. Lindenmayer, A.: Mathematical models for cellular interaction in development, Parts I and II. Journal of Theoretical Biology 18, 280–315 (1968)

    Article  Google Scholar 

  10. Lohn, J. D., Reggia, J. A.: Automatic discovery of self-replicating structures in cellular automata. IEEE Transactions on Evolutionary Computation 1(3), 165–178 (1997)

    Article  Google Scholar 

  11. Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ (1967)

    MATH  Google Scholar 

  12. Prusinkiewicz, P., Lindenmayer, A.: The Algorithmic Beauty of Plants. Springer-Verlag, New York (1990)

    MATH  Google Scholar 

  13. Rozenberg, R. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations. World Scientific (1997)

    Google Scholar 

  14. Salzberg, C., Sayama, H., Ikegami, T.: A tangled hierarchy of graph-constructing graphs. In: Proc. Ninth International Conference on the Simulation and Synthesis of Living Systems (Artificial Life IX), pp. 495–500, MIT Press, Cambridge, MA (2004)

    Google Scholar 

  15. Sayama, H.: Generative network automata: A generalized framework for modeling complex dynamical systems with autonomously varying topologies. In: Proc. 2007 IEEE Symposium on Artificial Life, pp. 214–221, IEEE Press, Los Alamitos, CA (2007)

    Google Scholar 

  16. Sipper, M.: Fifty years of research on self-replication: An overview. Artificial Life 4(3) 237–257 (1998)

    Article  Google Scholar 

  17. Smith, D. M. D., Onnela, J.-P., Lee, C. F., Fricker, M., Johnson, N. F.: Network automata and the functional dynamic network framework. arXive:physics/0701307v2 (2007)

    Google Scholar 

  18. Tomita, K., Kurokawa, H., Murata, S.: Graph automata: natural expression of self-reproduction. Physica D 171(4), 197–210 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Tomita, K., Kurokawa, H., Murata, S.: Automatic generation of self-replicating patterns in graph automata. International Journal of Bifurcation and Chaos 16(4), 1011–1018 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  20. Tomita, K., Murata, S., Kurokawa, H.: Self-description for construction and computation on graph-rewriting automata. Artificial Life 13, 383–396 (2007)

    Article  Google Scholar 

  21. Tomita, K., Murata, S., Kurokawa, H.: Asynchronous graph-rewriting automata and simulation of synchronous execution. Lecture Notes in Computer Science 4648, 865–876 (2007)

    Article  Google Scholar 

  22. Turing, A. M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Mathematical Society, Series 2, 42(2) 230–265 (1936)

    MATH  Google Scholar 

  23. von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Urbana (1966)

    Google Scholar 

  24. Wolfram, S.: Cellular Automata and Complexity. Addison-Wesley, Boston, MA (1994)

    MATH  Google Scholar 

  25. Wolfram, S.: A New Kind of Science. Wolfram Media, Champaign, IL (2002)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Institute of Advanced Industrial Science and Technology (AIST), 1-2-1 Namiki, 305-8564, Tsukuba, Ibaraki, Japan

    Kohji Tomita & Haruhisa Kurokawa

  2. Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Technology, Tokyo Institute of Technology, 4259 Nagatsuda, 226-8502, Midori-ku, Yokohama, Japan

    Satoshi Murata

Authors
  1. Kohji Tomita
    View author publications

    Search author on:PubMed Google Scholar

  2. Haruhisa Kurokawa
    View author publications

    Search author on:PubMed Google Scholar

  3. Satoshi Murata
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Kohji Tomita .

Editor information

Editors and Affiliations

  1. MPI für Physik Komplexer Systeme, Nöthnitzer Str. 38, Dresden, 01187, Germany

    Thilo Gross

  2. Binghamton University, State University of New York, Binghamton, 13902-6000, U.S.A.

    Hiroki Sayama

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Tomita, K., Kurokawa, H., Murata, S. (2009). Graph-Rewriting Automata as a Natural Extension of Cellular Automata. In: Gross, T., Sayama, H. (eds) Adaptive Networks. Understanding Complex Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01284-6_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-01284-6_14

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-01283-9

  • Online ISBN: 978-3-642-01284-6

  • eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)

Publish with us

Policies and ethics