Gem-graph/theory.en.md

Rewritten Geometric Directed Multigraphs Properties. (dec 2017)

Space, objects. Is a discrete space, whose cells have sites (syn: vessels, quivers, slots, locations, space holders) directed towards the neighboring cells. These sites may contain zero, one or several arrows that can be stacked and directed towards the same neighboring cell. Any distribution of arrows in the sites is a directed multigraph. It defines a state of the space. The cell is the smallest unit of space. All cells are similar. All have the same number of sites. Each cell can have at most as many sites as there are other cells in space. The site zero is directed toward the cell itself. Each cell designated by an arrow can itself contain zero, one or several arrows.

An object is an isolated connex part of this graph. Each state space, unless the space is empty or saturated, describes at least one object. According to the number of dimensions of the space, objects of any shape can be drawn: monomers, polymers, strings, knots, surfaces, volumes, cavities, fluids, basic machines, etc ... They can be combined in the same space to describe situations.

Transition rules A transition rule associates several elementary rules in any order. Each elementary rule associates a condition and an assignment. Both concern the same site in the same cell. A condition associates the coordinates of a site in a cell to a number (c). If the number of arrows in this site is equal to (c), then the condition is satisfied. Else, it is not. An assignment associates the coordinates of a site in a cell to a number (a). If the assignment is performed, then the number of arrows that contains this site becomes equal to (a). An elementary rule can alter or not the state of space. A transition rule must have at least an elementary rule and must not involve more than one of them on the same site.

Each transition rule defines two states of the space: one initial and one final. It completely defines them if it combines as many elementary rules as there are sites in the space. Else, it defines them partially or locally. Conversely, for any pair formed of any two states of the space there is always one rule and only one which describes the transition from the first one to the other.

Rewriting the graph allows to associate to each object or group of objects any motion, deformation, transport or transformation that gives it a variety of properties: strength, flexibility, elasticity, permeability, fluidity, viscosity, etc ... Directed arrows towards empty cells can be used to generate random connections that can mimick structural defects or mutations. Any objects interactions can be described.

Transition rules' properties For any state, there is a single neutral transition rule that does not alter that state. Any transition rule has a single inverse rule that produces its initial state from its final state. Given two rules (a) and (b) with the final state of (a) equal to the initial state of (b), there exists a single rule (c) (said 'composed') from the initial state of (a) to the final state of (b). If this rule (c) is part of the automaton, passing through the state between (a) and (b) is optional. It is necessary otherwise. In this case, the rule (a) will always be executed before the rule (b). Therefore, the property modelized by the rule (a) can be interpreted as a cause of the property modelized by the rule (b). Given three rules (a), (b) and (c) with the final state of (a) equal to the initial state of (b) and the final state of (b) equal to the initial state of (c) there is a single transition rule from the initial state of (a) to the final state (c). This rule can be produced by the successive compositions of (a * b) * c as well as of a * (b * c). (associativity) The area of a rule consists in all the cells containing a site on which there is a condition provided that no cell will be amended by an assignment without first being tested by at least one condition.

Automaton A spatial automaton is a set of transition rules associated with an initial state of space. All the static information is in the space. All the dynamic information is in the rules. The automaton uses no other information. It must contain at least one transition rule and should not associate two identical ones. The transitions are local and asynchronous. They may be performed in parallel if their areas do not overlap. They are Markov processes. During a transition, all the transition rules are evaluated. If several, with the same set of conditions, can apply, one of them is selected at random or according any other algorithm. If several, with different sets of conditions, can apply, the one with the greatest number of conditions apply.

Transitions tree All transition rules of the same automaton can be grouped into a single tree: the conditions tree. This tree can be created automatically from any list of rules. Each rule is written in the tree as a path from the root to a leaf. This path lists all the conditions that must be met for this transition rule to be applied. It can also lists nodes that contain no condition for this rule but some conditions for other rules. Why is this ? The set of conditions of all the rules define a space which is named the local space. To recognize if a rule can apply, all the conditions of this rule must be checked. But when this research is done simultaneously for all the rules through the condition's tree, a sequence search has to be defined on the set of all the sites of all the cells of the local space in order to avoid checking several times the same site. This sequence search order is arbitrary and several orders can (and should) be compared. Whatever the search algorithm used, it has to establish a path that enumerate all the sites of all the cells of the local space at least once and once only. Using this enumeration or path, the search of a convenient rule through the conditions'tree proceeds as follows: At each step of the path is a site of a cell of the local space. At each step of this path is also a depth level of the conditions'tree. The number of arrows contained in the site is compared to the conditions of the various rules at this depth level. If no rules has a condition on the number of arrows contained in this site, the site is skipped and the search goes on to the next site and to the next depth level. The branch that links a node whith no conditions to the following node (or level) is called a neutral branch.
Plus il y a de règles (moins il y a d’incertitude face à une situation), meilleure est la performance. If a rule contains a condition on the site, then the search follows a branch whose number equals the number of arrows that met its condition for that site. To summarize, two rules follow the same path starting from the root as long as they share the same conditions. When they differ on one condition, they then follow two different branches. To each site on which a rule has a condition corresponds at least one node. Each node may have as many branches as there may be arrows in a site (including zero) plus one. This branch, known as neutral, is followed by the rules that have no conditions on this site but still have some conditions further.

Performances Speed depend on the average depth of the transitions tree and on number of neutral branches. If all the possible situations are each described by a rule, there are no neutral branches and the performance is proportional to the average depth of the transitions tree. The more rules (the less uncertainty about a situation), the better the performance. The maximal depth of the tree cannot exceed the number of sites the the local space contains. If some possible situations are not described by a rule, there are neutral branches. Then, exploring the local space may not lead to any change. The more neutral branches, the longer the exploration of the tree. This is because the nodes that have a neutral branch may need to be explored several times, if the exploration of their non-neutral branches fails. Speed depends lesser on the size of the area covered by the set of transition rules. This size mainy limits the number of possible parallel processes in the space.

Granularity is not set once for all. It is possible to simultaneously manage both near and distant objects or parts of objects by combining arrows of short and long range. These allow to detail local areas of interest within a situation grossly described and to associate various levels of granularity up to an approximation of a continuous space. Using arrows, it is also possible to write in the space specific tags that can be associated to any objects or situations. This technique allows to keep a clear separation between static and dynamic information. This separation is the condition of an unique rules design which allows, in turn, their automatic rewriting.

Addition of automata Several automata can be added under the condition that their spaces share the same dimension and the same paving. Objects coming from different models can then be drawn in the same space to build a new initial state. All the rules, as they use the same formalism, can be grouped in the same tree. During the addition process, redundancies or conflicts can appear. Redundancies occur when two rules coming from different models do identical operations on identical situations, Only one instance of them should be kept. Conflicts appear when a rule of one model does an unwanted operation on some objects or situations of another model. This can be due to an inadequate description by the rules. Two kind of solutions are then possible and non exclusive: modify the objects shapes and / or add some new conditions to some rules in order to restrain their domain of application. If the model representations are correct, then the conflicts reveals a contradiction between the models themselves: an operation performed by one model is unwanted in the other. Conflicts can also appear when an unique object is associated to several different tags (tags can be used as keys)

Prospects

• Automatic production (by IA) of sets of transition rules from the graphic definition of initials and finals states.
• Graphic help for the edition of individual rules from schematic drawings of situations.
• Addition of objects and rules from multiple independent models. This property could allow to integrate models designed or developed by different teams working in parallel on separate mechanisms involving the same objects. Meta-rules could help to detect uncomplete or incompatible rules.
• The random production of rules may have an interest in learning models or evolution. Meta-rules can be used to eliminate poorly constructed rules before execution.
• Approximations of conservation laws.