  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 system.
