Correct and Complete (Positive) Strategy Annotations for OBJ

✍ Scribed by María Alpuente; Santiago Escobar; Salvador Lucas

• Book ID: 104445787
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 318 KB
• Volume: 71
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)82529-0

✦ Synopsis

Strategy annotations are used in several rewriting-based programming languages to introduce replacement restrictions aimed at improving efficiency and/or reducing the risk of nontermination. Unfortunately, rewriting restrictions can have a negative impact on the ability to compute normal forms. In this paper, we first ascertain/clarify the conditions ensuring correctness and completeness (regarding normalization) of computing with strategy annotations. Then, we define a program transformation methodology for (correct and) complete evaluations which applies to OBJ-like languages.