Introduction

This document is an introduction to Graph-Rewriting Automata (GRA).

GRA are an extension of Cellular Automata to a dynamic structure using local graph-rewriting rules. In this framework, initially simple graphs can evolve into complex self-organized structures. GRA display complex behaviors and can thus constitute a useful model of natural phenomena.

A Graph-Rewriting Automaton consists of:

• an initial graph \(G_0\) defined at time step \(t=0\),

• a rule to iteratively evolve it to any discrete time step \(t>0\).

\(G_t\) is the graph obtained at time \(t\).

In the following, a linear algebra based approach to GRA will be presented along with code examples.

Important

The code examples relie on the GRA python package. To install it on your computer, type the following command in your terminal.

pip install gra

Note

The concepts presented here are in the continuity of a previous work [1] that was implemented in Mathematica. This code can be found in a dedicated GitHub repository. The new python implementation leverages TensorFlow for GPU accelerated computations and has more functionality. However, since Mathematica offers more appropriate graph plotting functions, it has been used to generate the plots of the Gallery section.