Technical Report CS0367

Title: Fairness in Term Rewriting Systems
Authors: S. Porat and N. Francez
Abstract: The notion of fair derivation in a term-rewriting system is introduced, whereby every rewrite rule enabled infinitely often along a derivation is infinitely often applied. A term-rewritinng system is fairly-terminating iff all its fair derivations are finite. The paper presents the following question: is it decidable, for an arbitrary ground term rewriting system, whether it fairly terminates or not? A positive answer is given for several subcases. The general case remains open.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion