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.
Type de document :
Pré-publication, Document de travail
Accepted for publication in MSCS (Mathematical Structures for Computer Science). 2013
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : Bruno Guillaume <>
Soumis le : jeudi 19 décembre 2013 - 15:37:43
Dernière modification le : jeudi 11 janvier 2018 - 06:23:32
Document(s) archivé(s) le : jeudi 20 mars 2014 - 11:55:59


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00921038, version 1


Guillaume Bonfante, Bruno Guillaume. Non-size increasing Graph Rewriting for Natural Language Processing. Accepted for publication in MSCS (Mathematical Structures for Computer Science). 2013. 〈hal-00921038〉



Consultations de la notice


Téléchargements de fichiers