Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Non-size increasing Graph Rewriting for Natural Language Processing

Guillaume Bonfante 1 Bruno Guillaume 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, 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 :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00921038
Contributor : Bruno Guillaume <>
Submitted on : Thursday, December 19, 2013 - 3:37:43 PM
Last modification on : Friday, August 9, 2019 - 10:34:04 AM
Long-term archiving on: : Thursday, March 20, 2014 - 11:55:59 AM

File

grew.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00921038, version 1

Collections

Citation

Guillaume Bonfante, Bruno Guillaume. Non-size increasing Graph Rewriting for Natural Language Processing. 2013. ⟨hal-00921038v1⟩

Share

Metrics

Record views

366

Files downloads

261