Non-simplifying Graph Rewriting Termination

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 : So far, a very large amount of work in Natural Language Processing (NLP) rely on trees as the core mathematical structure to represent linguistic informations (e.g. in Chomsky's work). However, some linguistic phenomena do not cope properly with trees. In a former paper, we showed the benefit of encoding linguistic structures by graphs and of using graph rewriting rules to compute on those structures. Justified by some linguistic considerations, graph rewriting is characterized by two features: first, there is no node creation along computations and second, there are non-local edge modifications. Under these hypotheses, we show that uniform termination is undecidable and that non-uniform termination is decidable. We describe two termination techniques based on weights and we give complexity bound on the derivation length for these rewriting systems.
Type de document :
Communication dans un congrès
Rachid Echahed and Detlef Plump. TERMGRAPH, Mar 2013, Rome, Italy. pp.4-16, 2013, 7th International Workshop on Computing with Terms and Graphs. 〈http://termgraph2013.imag.fr/pages/TERMGRAPH2013Proceedings.pdf〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00921053
Contributeur : Bruno Guillaume <>
Soumis le : jeudi 19 décembre 2013 - 15:48:58
Dernière modification le : jeudi 11 janvier 2018 - 06:23:32
Document(s) archivé(s) le : jeudi 20 mars 2014 - 12:00:22

Fichier

termgraph.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00921053, version 1

Citation

Guillaume Bonfante, Bruno Guillaume. Non-simplifying Graph Rewriting Termination. Rachid Echahed and Detlef Plump. TERMGRAPH, Mar 2013, Rome, Italy. pp.4-16, 2013, 7th International Workshop on Computing with Terms and Graphs. 〈http://termgraph2013.imag.fr/pages/TERMGRAPH2013Proceedings.pdf〉. 〈hal-00921053〉

Partager

Métriques

Consultations de la notice

339

Téléchargements de fichiers

165