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.
Type de document :
Article dans une revue
Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2018, 28 (08), pp.1451 - 1484. 〈10.1017/S0960129518000178〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Bruno Guillaume <>
Soumis le : jeudi 22 novembre 2018 - 10:08:23
Dernière modification le : mardi 18 décembre 2018 - 16:38:01


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers