Non-simplifying Graph Rewriting Termination - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Non-simplifying Graph Rewriting Termination

Résumé

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.
Fichier principal
Vignette du fichier
termgraph.pdf (338.97 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00921053 , version 1 (19-12-2013)

Identifiants

  • HAL Id : hal-00921053 , version 1

Citer

Guillaume Bonfante, Bruno Guillaume. Non-simplifying Graph Rewriting Termination. TERMGRAPH, Mar 2013, Rome, Italy. pp.4-16. ⟨hal-00921053⟩
202 Consultations
166 Téléchargements

Partager

Gmail Facebook X LinkedIn More