Gem-graph/theory.md

Réécriture des multigraphes dirigés géométriques. Propriétés, applications.

(déc 2017, mars 2024)

Espace, objets.

L'espace est discret, newtonien et euclidien. Sa représentation est cartésienne. Ses cellules possèdent des sites dirigés vers les cellules voisines et peuvent avoir un site dirigé vers elles-mêmes. Le nombre et l'attribution de ces sites définit le voisinage : à chaque cellule voisine (pas nécessairement adjacente) est associé un site et un seul. Ces sites peuvent contenir zéro, une ou plusieurs flèches. Toute distribution de flèches dans les sites est un multigraphe dirigé. Elle définit un état de l'espace. La cellule est la plus petite unité de l'espace. Toutes les cellules sont semblables. Elles ont toutes le même nombre de sites. Chaque cellule peut avoir au plus autant de sites qu'il y a d'autres cellules dans l'espace. Une cellule désignée par une flèche provenant d'une cellule voisine peut elle-même contenir zéro, une ou plusieurs flèches réparties dans ses propres sites.

Un objet est une partie connexe isolée de ce graphe. Chaque espace d'état, sauf si cet espace est vide ou saturé, décrit au moins un objet. Selon le nombre de dimensions de l'espace, on peut dessiner des objets de forme quelconque : monomères, polymères, cordes, nœuds, surfaces, volumes, cavités, etc. Les objets peuvent être combinés dans un même espace pour décrire des situations : fluides, solides, machines élémentaires, etc.

Règles de transition.

Une règle de transition associe plusieurs règles élémentaires dans un ordre quelconque. Chaque règle élémentaire associe une condition et une assignation. Les deux concernent le même site dans la même cellule. Une condition associe les coordonnées d'un site dans une cellule à un nombre (c). Si le nombre de flèches de ce site est égal à (c), alors la condition est satisfaite. Sinon, elle ne l'est pas. Une assignation associe les coordonnées d'un site dans une cellule à un nombre (a). Si l'assignation est réalisée, alors le nombre de flèches qui contient ce site devient égal à (a). Une règle élémentaire peut modifier ou non l'état de l'espace. Une règle de transition doit comporter au moins une règle élémentaire et ne doit pas en comporter plus d'une concernant un même site.

Chaque règle de transition définit deux états de l'espace : un initial et un final. Elle les définit complètement si elle combine autant de règles élémentaires qu'il y a de sites dans l'espace. Sinon, elle les définit partiellement ou localement. Inversement, pour toute paire formée de deux états quelconques de l'espace, il existe toujours une règle et une seule qui décrit la transition du premier à l'autre.

La réécriture du graphe permet d'associer à chaque objet ou groupe d'objets un mouvement, une déformation, un transport ou une transformation qui lui confère des propriétés variées : force, flexibilité, élasticité, perméabilité, fluidité, viscosité, etc... Des flèches dirigées vers des cellules vides peuvent être utilisées pour générer des connexions aléatoires qui peuvent mimer des défauts structurels ou des mutations. Toutes les interactions entre objets peuvent être décrites.

Propriétés des règles de transition.

Pour tout état, il existe une seule règle de transition neutre qui ne modifie pas cet état. Toute règle de transition a une seule règle inverse qui produit son état initial à partir de son état final. Étant donné deux états (1) et (2) il existe toujours au moins une règle de transition produisant l'état (2) à partir de l'état (1) L'une de ces règles est la plus simple possible. Étant donné deux règles (a) et (b) dont l'état final de (a) est égal à l'état initial de (b), il existe une seule règle (c) (dite "composée") qui va de l'état initial de (a) à l'état final de (b). Si cette règle (c) fait partie de l'automate, le passage par l'état entre (a) et (b) est facultatif. Sinon, il est nécessaire. Dans ce cas, la règle (a) sera toujours exécutée avant la règle (b). Par conséquent, la propriété modélisée par la règle (a) peut être interprétée comme une cause de la propriété modélisée par la règle (b). Étant donné trois règles (a), (b) et (c) avec l'état final de (a) égal à l'état initial de (b) et l'état final de (b) égal à l'état initial de (c), il existe une seule règle de transition de l'état initial de (a) à l'état final (c). Cette règle peut être produite par les compositions successives de (a * b) * c ainsi que de a * (b * c). (associativité) L'aire d'une règle est constituée par l'ensemble des cellules contenant un site sur lequel il existe une condition à condition qu'aucune cellule ne soit modifiée par une assignation sans avoir été préalablement testée par au moins une condition.

Automate.

Un automate spatial est un ensemble de règles de transition associées à un état initial de l'espace. Toute l'information statique est dans l'espace. Toute l'information dynamique se trouve dans les règles. L'automate n'utilise aucune autre information. Il doit contenir au moins une règle de transition et ne doit pas en associer deux identiques. Les transitions sont locales et asynchrones. Elles peuvent être réalisées en parallèle si leurs zones ne se chevauchent pas. Elles sont des processus de Markov. Lors d'une transition, toutes les règles de transition sont évaluées. Si plusieurs peuvent s'appliquer, l'une d'entre elles est choisie au hasard ou selon tout autre algorithme.

Arbre des conditions.

Toutes les règles de transition d'un même automate peuvent être regroupées en un seul arbre : l'arbre des conditions. Cet arbre peut être créé automatiquement à partir d'une liste de règles. Chaque règle est inscrite dans l'arbre sous la forme d'un chemin allant de la racine à une feuille. Ce chemin liste toutes les conditions qui doivent être remplies pour que cette règle de transition soit appliquée. Dans chaque chemin, l'ordre des conditions est le même. Il fait référence à un ordre défini précédemment sur l'ensemble des sites de toutes les cellules où une règle élémentaire peut s'appliquer. Cet ordre est le même pour toutes les règles. A chaque noeud, chaque règle de transition suit la branche dont le numéro est égal au nombre de flèches qui ont satisfait à sa condition pour ce site. Deux règles suivent le même chemin à partir de la racine tant qu'elles partagent les mêmes conditions. Lorsqu'elles diffèrent sur une condition, elles suivent alors deux branches différentes. A chaque site sur lequel une règle a une condition correspond au moins un noeud. Chaque nœud peut avoir autant de branches qu'il peut y avoir de flèches dans un site (y compris zéro) plus une. Cette branche, dite neutre, est suivie par les règles qui n'ont pas de condition sur ce site mais qui ont tout de même des conditions qui n'ont pas été évaluées jusqu'ici lors du parcours de l'arbre.

Performances.

La vitesse dépend de la profondeur moyenne de l'arbre des transitions et du nombre de branches neutres. Si toutes les situations possibles sont chacune décrites par une règle, il n'y a pas de branches neutres et la performance est proportionnelle à la profondeur moyenne de l'arbre des transitions. La profondeur maximale de l'arbre ne peut pas dépasser le nombre de sites que contient l'espace de travail. Si certaines situations possibles ne sont pas décrites par une règle, il y a des branches neutres. Dans ce cas, l'exploration de l'espace de travail peut ne conduire à aucun changement. Plus il y a de branches neutres, plus l'exploration de l'arbre est longue. En effet, les nœuds qui ont une branche neutre doivent éventuellement être explorés plusieurs fois. Cela se produit si l'exploration de leurs branches non neutres échoue ou si plusieurs transitions sont possibles à partir de ce nœud avec chacune une probabilité inférieure à 1 (leur somme étant égale à 1). La vitesse dépend aussi de la taille de la zone couverte par l'ensemble des règles de transition (l'espace de travail). Cette taille limite principalement le nombre de processus parallèles possibles dans l'espace.

La granularité n'est pas fixée une fois pour toutes. Il est possible de gérer simultanément des objets ou parties d'objets proches et lointains en combinant des flèches de courte et longue portée. Celles-ci permettent de détailler des zones d'intérêt locales au sein d'une situation décrite de manière globale et d'associer différents niveaux de granularité jusqu'à une approximation d'un espace continu. En utilisant les flèches, il est également possible d'inscrire dans l'espace des étiquettes spécifiques qui peuvent être associées à n'importe quel objet ou situation. Cette technique permet de maintenir une séparation claire entre les informations statiques et dynamiques eu utilisant le "pattern recogniion". Cette séparation est la condition d'une conception unique des règles qui permet, à son tour, leur réécriture automatique.

Ajout d'automates.

Plusieurs automates peuvent être ajoutés à condition que leurs espaces partagent la même dimension et le même pavage. Des objets provenant de modèles différents peuvent alors être dessinés dans le même espace pour construire un nouvel état initial. Toutes les règles, puisqu'elles utilisent le même formalisme, peuvent être regroupées dans un même arbre. Au cours du processus d'addition, des redondances ou des conflits peuvent apparaître. Les redondances se produisent lorsque deux règles provenant de modèles différents effectuent des opérations identiques sur des situations identiques, une seule instance de ces règles doit être conservée. Les conflits apparaissent lorsqu'une règle d'un modèle effectue une opération non désirée sur certains objets ou situations d'un autre modèle. Cela peut être dû à une description inadéquate par les règles. Deux types de solutions sont alors possibles et non exclusives : modifier les formes des objets et/ou ajouter de nouvelles conditions à certaines règles afin de restreindre leur domaine d'application. Si les représentations des modèles sont correctes, alors les conflits révèlent une contradiction entre les modèles eux-mêmes : une opération effectuée par un modèle n'est pas souhaitée par l'autre. Des conflits peuvent également apparaître lorsqu'un objet unique est associé à plusieurs tags différents (les tags peuvent être utilisés comme des clés).

Un modèle gem-graph peut être associé à une description continue (par équations différentielles) d'une répartiotion de fermions et à des phénomènes décrits par des bosons. Dans ces deux cas, une condition et une action spécifique sont nécéssaires.

Perspectives.

• Production automatique (par IA) d'ensembles de règles de transition à partir de la définition graphique des états initiaux et finaux.
• Aide graphique pour l'édition de règles individuelles à partir de dessins schématiques de situations.
• Ajout d'objets et de règles à partir de plusieurs modèles indépendants. Cette propriété pourrait permettre d'intégrer des modèles conçus ou développés par différentes équipes travaillant en parallèle sur des mécanismes distincts impliquant les mêmes objets. Les méta-règles pourraient aider à détecter les règles incomplètes ou incompatibles.
• La production aléatoire de règles peut avoir un intérêt pour l'apprentissage de modèles ou l'évolution. Les méta-règles peuvent être utilisées pour éliminer les règles mal construites avant leur exécution.
• Approximations des lois de conservation.