Drags: A Simple Algebraic Framework For Graph Rewriting

Abstract : We are interested here in a natural generalization of term rewriting techniques to what we call drags, viz. finite, directed, ordered multigraphs. Each vertex is labeled by a function symbol, the arity of which governs the number of vertices to which it relates by an incoming edge in the graph. To this end, we develop a rich algebra of drags which generalizes the familiar term algebra and its associated rewriting capabilities. Viewing graphs as terms provides an initial building block for rewriting with such graphs, that should impact the many areas where computations take place on graphs.
Type de document :
Communication dans un congrès
TERMGRAPH 2018 - 10th International Workshop on Computing with Terms and Graphs, Jul 2018, Oxford, United Kingdom
Liste complète des métadonnées

https://hal.inria.fr/hal-01853836
Contributeur : Jean-Pierre Jouannaud <>
Soumis le : dimanche 5 août 2018 - 12:06:15
Dernière modification le : mercredi 22 août 2018 - 09:40:08

Fichier

GraphRewritingTG-Final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01853836, version 1

Citation

Nachum Dershowitz, Jean-Pierre Jouannaud. Drags: A Simple Algebraic Framework For Graph Rewriting. TERMGRAPH 2018 - 10th International Workshop on Computing with Terms and Graphs, Jul 2018, Oxford, United Kingdom. 〈hal-01853836〉

Partager

Métriques

Consultations de la notice

93

Téléchargements de fichiers

9