Skip to Main content Skip to Navigation

On termination of Graph Rewriting Systems through language theory

Guillaume Bonfante 1 Miguel Couceiro 2
1 CARBONE - Carbone
LORIA - FM - Department of Formal Methods
2 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : The termination issue we tackle is rooted in natural language processing where graph rewriting systems (GRS) may contain a large number of rules, often in the order of thousands. Decidable concepts thus become mandatory to verify the termination of such systems. The notion of graph rewriting consider does not make any assumption on the structure of graphs (they are not “term graphs”, “port graphs” nor drags). The lack of algebraic structure in our setting led us to proposing two orders on graphs inspired from language theory: the matrix multiset-path order and the rational embedding order. We show that both are stable by context, which we then use to obtain the main contribution of the paper: under a suitable notion of “interpretation”, a GRS is terminating if and only if it is compatible with an interpretation.
Complete list of metadatas

https://hal.inria.fr/hal-02478696
Contributor : Miguel Couceiro <>
Submitted on : Friday, February 14, 2020 - 9:45:04 AM
Last modification on : Tuesday, March 3, 2020 - 1:17:05 AM

File

terminaison.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02478696, version 1

Citation

Guillaume Bonfante, Miguel Couceiro. On termination of Graph Rewriting Systems through language theory. 2020. ⟨hal-02478696⟩

Share

Metrics

Record views

25

Files downloads

86