University of Illinois Urbana-Champaign

The Temporal Logic of Rewriting

Meseguer, José

Content Files
The Temporal Logic of Rewriting.pdf

Permalink

https://hdl.handle.net/2142/11293

Description

Title
The Temporal Logic of Rewriting
Author(s)
Meseguer, José
Issue Date
2007-02
Keyword(s)
  • computer science
  • rewriting
Date of Ingest
2009-04-21T20:17:05Z
Abstract
This paper presents the temporal logic of rewriting TLR*. Syntactically, TLR* is a very simple extension of CTL* which just adds action atoms, in the form of spatial action patterns, to CTL*. Semantically and pragmatically, however, when used together with rewriting logic as a ``tandem'' of system specification and property specification logics, it has substantially more expressive power than purely state-based logics like CTL*, or purely action-based logics like A-CTL*. Furthermore, it avoids the system/property mismatch problem experienced in state-based or action-based logics, which makes many useful properties inexpressible in those frameworks without unnatural changes to a system's specification. The advantages in expresiveness of TLR* are gained without losing the ability to use existing tools and algorithms to model check its properties: a faithful translation of models and formulas is given that allows verifying TLR* properties with CTL* model checkers. Simulations and bisimulations reflecting and/or preserving useful classes of TLR* properties are also studied. Finally, a strategy language for rewriting is used as a way to verify (resp. falsify) guarantee (resp. safety) formulas in TLR* for infinite-state systems and, more generally, to verify strategy formulas about such systems using semidecision procedures.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11293
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

Research and Tech Reports - Computer Science PRIMARY