A selforganization at a sequential growth of a directed acyclic dyadic graph
Scientific Research Institute for System Analysis of the Russian Academy of Science, 117218, Nahimovskiy pr., 36, k. 1, Moscow, Russia1 pp. (accepted)
A directed acyclic graph is considered as a model of discrete process. Such process consists of a discrete set of events. Vertices of graph represent events. Directed paths represent causal connections of events. The absence of directed cyclic paths (an acyclicity) describes causality. Such kind of models can be used in different areas of investigation. For example, such model can describe a computer program execution. A far task of present investigation is to develop a discrete model of spacetime at microscopic level.
A given graph is a model of known part of process. The aim of dynamics is to predict a future of the process or to reconstruct the past. This means to add new parts to the graph. The minimal addition is a vertex. We can represent any addition as a sequential addition of vertices one by one.
A selforganization is an interesting problem of sequential growth dynamics of graph. In a discrete model of spacetime, selforganized quasirepetitive structures can be considered as models of particles. Usually a selforganization is considered in continual systems by using nonlinear differential equations. A discrete model of selforganization usually is a cellular automaton with deterministic evolution. A feature of considered approach is nondeterministic dynamics. The structure of given graph determines probabilities of different variants of addition of new vertex.
The particular case is a dyadic graph. In this graph, each vertex has no more than two incident incoming edges and two incident outgoing edges . Different variants of sequential growth are considered. The algorithms to calculate probabilities of variants to add a new vertex depend on a calculation of paths in the graph. We get examples with a selforganization by a numerical simulation. In one simple case, we find out a selforganization analytically.
1. Krugly, A. L., A sequential growth dynamics for a directed acyclic dyadic graph, arXiv: 1112.1064 [gr-qc].