E-graph

E-graph

Un E-Graph en informatique est une structure de donnée servant à déterminer si une égalité peut être la conséquence de plusieurs autres égalités, et ceci de manière purement syntaxique.

On considère un ensemble d'égalité sur des termes sur un alphabet donné ayant des applications, des symboles et des variables. On souhaite savoir si une égalité entre deux termes est vraie ou fausse.

Sommaire

Création du graphe

On considère que les termes sont représentés par des graphes orientés acyclique. La représentation est définie de manière récursive sur la hauteur des termes. Chaque constante (ou variable) est représentée par une feuille étiquetée par cette constante (ou variable), et les applications à n éléments d'un symbole f sont représentées par n arcs partant d'une racine étiquetée f vers les arbres représentant ces n sous-termes. Ces n arcs sont numérotés de 1 à n de manière à éviter que deux fonctions appliquées aux mêmes termes mais dans un ordre différent ne soient représentées par le même arbre.

Il faut bien voir qu'il y a autant de nœuds étiquetés par f qu'il y a d'applications de f à des termes différents, par contre quand deux termes sont identiques on considère qu'ils ont le même arbre. L'égalité sur les termes est donc équivalente à l'égalité sur des arbres.

Rajout des égalités

Une fois qu'on a créé autant d'arbres qu'il fallait pour les termes qui appartiennent aux hypothèses et à la conclusion recherchée, on passe à une deuxième étape.

On initialise une structure d'union-find uf, dans laquelle on fait une union entre chaque terme égaux.

Pour chaque couple de nœud ayant la même étiquette et le même nombre n de fils, on regarde si leurs ième fils sont égaux pour selon uf, pour tout i entre 1 et n. Si c'est le cas, alors on fait l'union de ces deux nœuds dans uf.

On itère cette étape jusqu'à trouver un point fixe. Celui-ci existe car à chaque étape le nombre d'égalité augmente et est majoré par n*(n-1) si n est le nombre de terme du graphe.

Réponse

Pour savoir si deux termes sont égaux, il suffit de rendre vrai s'ils sont égaux selon uf, et de renvoyer la réponse.

Amélioration

Il va de soi qu'en plus de cet algorithme, de multiples améliorations sont possibles pour l'implémentation, telles que :

  • s'arrêter dès qu'on a prouvé l'égalité que l'on voulait montrer ;
  • commencer par créer des ensemble de tous les nœuds ayant la même étiquette afin de diminuer le temps pris par l'itération ;
  • garder la structure du E-graph en mémoire pour pouvoir éventuellement tester des égalités entre d'autre termes, et potentiellement rajouter de nouvelles égalités ou de nouveaux termes.

Extension

Il faut remarquer que si l'algorithme répond non, cela ne signifie pas que deux termes sont différents, mais simplement qu'on ne peut pas prouver qu'ils sont égaux avec les axiomes donné faites.

Pour remédier à cela, on peut rajouter des hypothèses de différences. Il faut alors rajouter des arête entre les classes d'uf pour représenter la différence.

Cela permettra de prouver l'incohérence s'il y a une arête "différente" sur une seule classe.

De la même façon, on peut rajouter des pré-ordres à l'aide d'un type d'arc distinct(en supposant que l'ordre passe au contexte). Si on ne peut pas trouver n1 et n2 tel que n1>n2 et n2>n1 alors c'est que le pré-ordre est un ordre sur l'ensemble de termes considéré.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article E-graph de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Graph pebbling — is a mathematical game and area of interest played on a graph with pebbles on the vertices. Game play is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an… …   Wikipedia

  • Graph paper — Regular graphing paper (upper); Logarithmic graphing paper (lower). Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a …   Wikipedia

  • Graph transformation — Graph transformation, or Graph rewriting, concerns the technique to create a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms.Graph… …   Wikipedia

  • Graph — (gr[.a]f), n. [See { graph}.] (Math.) 1. A curve or surface, the locus of a point whose co[ o]rdinates are the variables in the equation of the locus; as, a graph of the exponential function. [Webster 1913 Suppl.] 2. A diagram symbolizing a… …   The Collaborative International Dictionary of English

  • Graph — may refer to:* A graphic (such as a chart or diagram) depicting the relationship between two or more variables used, for instance, in visualising scientific data.In mathematics:* Graph (mathematics), a set of vertices connected with edges * Graph …   Wikipedia

  • Graph Modelling Language — (GML) is a hierarchical ASCII based file format for describing graphs. Applications supporting GML * Cytoscape, an open source bioinformatics software platform for visualizing molecular interaction networks, loads and save previously constructed… …   Wikipedia

  • graph´ic|ness — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph´ic|ly — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph´i|cal|ly — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph|ic — «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • Graph — 〈m. 16; Math.〉 = Graf2 * * * 1Graph , Graf , der; en, en [zu griech. gráphein = schreiben] (bes. Math., Naturwiss.): grafische Darstellung (z. B. von Relationen) in Form von [markierten] Knoten[punkten] u. verbindenden Linien (Kanten). 2Graph,… …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”