Skip to Main content Skip to Navigation
Conference papers

Graph Path Orderings

Abstract : We define well-founded rewrite orderings on graphs and show that they can be used to show termination of a set of graph rewrite rules by verifying all their cyclic extensions. We then introduce the graph path ordering inspired by the recursive path ordering on terms and show that it is a well-founded rewrite ordering on graphs for which checking termination of a finite set of graph rewrite rules is decidable. Our ordering applies to arbitrary finite, directed, labeled, ordered multigraphs, hence provides a building block for rewriting with graphs, which should impact the many areas in which computations take place on graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Jean-Pierre Jouannaud Connect in order to contact the contributor
Submitted on : Thursday, January 10, 2019 - 8:17:50 AM
Last modification on : Monday, February 15, 2021 - 10:48:54 AM
Long-term archiving on: : Thursday, April 11, 2019 - 2:48:03 PM


GraphPathOrderingLPAR (1).pdf
Files produced by the author(s)


  • HAL Id : hal-01903086, version 1


Nachum Dershowitz, Jean-Pierre Jouannaud. Graph Path Orderings. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Nov 2018, Awassa, Ethiopia. pp.1-18. ⟨hal-01903086⟩



Record views


Files downloads