Stochastic Evolution via Graph Grammars
Résumé
This is the second part in the series of papers where we are looking for new connections between computer science, mathematics and physics. These connectio- ns go through the central notions of computer science - grammar and graph grammar. In section 2 main definitions concerning random graph grammars are given. Section 3 and 4 are devoted to the simplest models of graph dynamics: we study the large time behaviour of local and global characteristic- s of growing one-dimensional complexes. Main emphasis is on looking for correct problems and models, discussing their qualitative behaviour. We consider asymptotic growth of the number of connected components, the degree of local compactness, topological chaos, phases of different topology etc. In section 4 we construct infinite cluster dynamics. We discuss some aspects which distinguish thermodynamic limit for graph grammars from that for Gibbs fields on a lattice. One of the central emerging notions is the statistically homogeneous infinite complex.