Quarterly (winter, spring, summer, fall)
128 pp. per issue
7 x 10, illustrated
2014 Impact factor:

Artificial Life

Fall 2007, Vol. 13, No. 4, Pages 383-396
(doi: 10.1162/artl.2007.13.4.383)
© 2007 Massachusetts Institute of Technology
Self-Description for Construction and Computation on Graph-Rewriting Automata
Article PDF (281.56 KB)

This article shows how self-description can be realized for construction and computation in a single framework of a variant of graph-rewriting systems called graph-rewriting automata. Graph-rewriting automata define symbol dynamics on graphs, in contrast to cellular automata on lattice space. Structural change is possible along with state transition. Self-replication based on a self-description is shown as an example of self-description for construction. This process is performed using a construction arm, which is realized as a subgraph, that executes a program described in the graph structure. In addition, a metanode structure is introduced to embed rule sets in the graph structure as self-description for computation. These are regarded as universal graph-rewriting automata that can serve as a model of systems that maintain themselves through replication and modification.