Non-size increasing Graph Rewriting for Natural Language Processing

Guillaume Bonfante 1 Bruno Guillaume 2
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
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00921038
Contributor : Bruno Guillaume <>
Submitted on : Thursday, November 22, 2018 - 10:08:23 AM
Last modification on : Tuesday, December 18, 2018 - 4:38:01 PM
Document(s) archivé(s) le : Saturday, February 23, 2019 - 1:11:16 PM

File

grew.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

54

Files downloads

56