Termination of Priority Rewriting - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2008

Termination of Priority Rewriting



Introducing priorities on rules in rewriting increases their expressive power and helps to limit computations. Priority rewriting is used in rule-based programming as well as in functional programming. Termination of priority rewriting is then important to guarantee that programs give a result. We describe in this paper an inductive proof method for termination of priority rewriting, relying on an explicit induction on the termination property. It works by generating proof trees, modeling the rewriting relation by using abstraction and narrowing. As it specifically handles priorities on the rules, our technique allows proving termination of term rewrite systems that would diverge without priorities.
Fichier principal
Vignette du fichier
IP-termin-hal.pdf (215.19 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00243131 , version 1 (23-05-2008)


  • HAL Id : inria-00243131 , version 1


Isabelle Gnaedig. Termination of Priority Rewriting. [Research Report] 2008, pp.13. ⟨inria-00243131⟩
81 View
110 Download


Gmail Facebook Twitter LinkedIn More