A Class of Rewriting Rules and Reverse Transformation for Rule-based Equivalent Transformation

✍ Scribed by Kiyoshi Akama; Ekawit Nantajeewarawat; Hidekatsu Koike

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 297 KB
• Volume: 59
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(04)00291-9

✦ Synopsis

In the rule-based equivalent transformation (RBET) paradigm, where computation is based on meaning-preserving transformation of declarative descriptions, a set of rewriting rules is regarded as a program. The syntax for a large class of rewriting rules is determined. The incorporation of meta-variables of two different kinds enables precise control of rewriting-rule instantiations. As a result, the applicability of rewriting rules and the results of rule applications can be rigorously specified. A theoretical basis for justifying the correctness of rewriting rules is established. Reverse transformation operation in the RBET framework is discussed, and it is shown that a correct rewriting rule is reversible, i.e., a correct rewriting rule can in general be constructed by syntactically reversing another correct rewriting rule.