Termination of Just/Fair Computations in Term Rewriting

Lucas, Salvador; Meseguer, José

Permalink

https://hdl.handle.net/2142/11296 Copy

Description

Title

Termination of Just/Fair Computations in Term Rewriting

Author(s)

• Lucas, Salvador
• Meseguer, José

Issue Date

2007-02

Keyword(s)

computer science

Abstract

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 reductionistic 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 methodology for proving fair-termination that can be automated and can be supported by current termination tools. We illustrate this methodology with some concrete examples and briefly comment on future extensions.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11296

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections