Termination of just/fair computations in term rewriting

Salvador Lucas, José Meseguer

Research output: Contribution to journalArticlepeer-review


The main goal of this paper is to apply rewriting termination technology-enjoying a quite mature set of termination results and tools-to the problem of proving automatically the termination of concurrent systems under fairness assumptions. We adopt the thesis that a concurrent system can be naturally modeled as a rewrite system, and develop a theoretical approach to systematically transform, under reasonable assumptions, fair-termination problems into ordinary termination problems of associated relations, to which standard rewriting termination techniques and tools can be applied. Our theoretical results are combined into a practical proof method for proving fair-termination that can be automated and can be supported by current termination tools. We illustrate this proof method with some concrete examples and briefly comment on future extensions.

Original languageEnglish (US)
Pages (from-to)652-675
Number of pages24
JournalInformation and Computation
Issue number5
StatePublished - May 2008


  • Concurrent programming
  • Fairness
  • Program analysis
  • Term rewriting
  • Termination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Termination of just/fair computations in term rewriting'. Together they form a unique fingerprint.

Cite this