Graph-rewriting automata as a natural extension of cellular automata

Kohji Tomita, Haruhisa Kurokawa, Satoshi Murata

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

11 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAdaptive Networks
Subtitle of host publicationTheory, Models and Applications
Number of pages19
Publication statusPublished - 2009

Publication series

NameUnderstanding Complex Systems
ISSN (Print)1860-0832
ISSN (Electronic)1860-0840


Dive into the research topics of 'Graph-rewriting automata as a natural extension of cellular automata'. Together they form a unique fingerprint.

Cite this