Well-founded Path Orderings for Drags

Abstract : The definition herein of the Graph Path Ordering (GPO) on certain graph expressions is inspired by that of the Recursive Path Ordering (RPO), and enjoys all those properties that have made RPO popular, in particular, well-foundedness and monotonicity on variable-free terms. We are indeed interested in a generalization of algebraic expressions called operadic expressions, which are finite graphs each vertex of which is labelled by a function symbol, the arity of which governs the number of vertices it relates to in the graph. These graphs are seen here as terms with sharing and back-arrows. Operadic expressions are themselves multiplied (an associative operation) to form monomials, which are in turn summed up (an associative commutative operation) to form polynomials. Operadic expressions and their polynomials occur in algebraic topology, and in various areas of computer science, notably concurrency and type theory. Rewriting basic operadic expressions is very much like rewriting algebraic expressions, while rewriting their monomials and polynomials is very much like the Groebner basis theory. GPO provides an initial building block for computing with operadic expressions and their polynomials.
Type de document :
Communication dans un congrès
Proceedings Higher Dimensional Rewriting and Applications, Jun 2016, Porto, Portugal. Easy Chair, Workshop HDRA, 2016, Higher Dimensional Rewriting and Applications
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01330907
Contributeur : Jean-Pierre Jouannaud <>
Soumis le : lundi 13 juin 2016 - 10:59:57
Dernière modification le : jeudi 10 mai 2018 - 02:06:50

Fichier

HDRA2016_paper_8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01330907, version 1

Citation

Nachum Dershowitz, Jean-Pierre Jouannaud, Jianqi Li. Well-founded Path Orderings for Drags. Proceedings Higher Dimensional Rewriting and Applications, Jun 2016, Porto, Portugal. Easy Chair, Workshop HDRA, 2016, Higher Dimensional Rewriting and Applications. 〈hal-01330907〉

Partager

Métriques

Consultations de la notice

110

Téléchargements de fichiers

58