Skip to Main content Skip to Navigation
Journal articles

Non-size increasing Graph Rewriting for Natural Language Processing

Guillaume Bonfante 1 Bruno Guillaume 2
1 CARBONE - Carbone
LORIA - FM - Department of Formal Methods
2 SEMAGRAMME - Semantic Analysis of Natural Language
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : A very large amount of work in Natural Language Processing use tree structure as the first class citizen mathematical structures to represent linguistic structures such as parsed sentences or feature structures. However, some linguistic phenomena do not cope properly with trees: for instance, in the sentence "Max decides to leave", "Max" is the subject of the both predicates "to decide" and "to leave". Tree-based linguistic formalisms generally use some encoding to manage sentences like the previous example. In former papers, we discussed the interest to use graphs rather than trees to deal with linguistic structures and we have shown how Graph Rewriting could be used for their processing, for instance in the transformation of the sentence syntax into its semantics. Our experiments have shown that Graph Rewriting applications to Natural Language Processing do not require the full computational power of the general Graph Rewriting setting. The most important observation is that all graph vertices in the final structures are in some sense "predictable" from the input data and so, we can consider the framework of Non-size increasing Graph Rewriting. In our previous papers, we have formally described the Graph Rewriting calculus we used and our purpose here is to study the theoretical aspect of termination with respect to this calculus. In our framework, we show that uniform termination is undecidable and that non-uniform termination is decidable. We define termination techniques based on weight, we prove the termination of weighted rewriting systems and we give complexity bounds on derivation lengths for these rewriting systems.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Bruno Guillaume Connect in order to contact the contributor
Submitted on : Thursday, November 22, 2018 - 10:08:23 AM
Last modification on : Wednesday, November 3, 2021 - 7:08:55 AM
Long-term archiving on: : Saturday, February 23, 2019 - 1:11:16 PM


Files produced by the author(s)



Guillaume Bonfante, Bruno Guillaume. Non-size increasing Graph Rewriting for Natural Language Processing. Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2018, 28 (08), pp.1451 - 1484. ⟨10.1017/S0960129518000178⟩. ⟨hal-00921038v2⟩



Les métriques sont temporairement indisponibles