2013/02/28 by Claude Kirchner, Hélène Kirchner
Computer Science · Mathematics · #Computer science #Confluence #Formal Methods in Verification #Function (biology) #Functional programming #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Path (computing) #Programming language #Reduction (mathematics) #Reduction strategy #Rewriting #Sequence (biology) #Term (time) #Theoretical computer science #cs.LO
paper · pdf · doi:10.4204/eptcs.112.15
published as EPTCS 112, 2013, pp. 99-105 · In Proceedings SR 2013, arXiv:1303.0071
openalex publication_date 2013/02/28 · arxiv created 2013/03/04 · arxiv updated 2013/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper is an expository contribution reporting on published work. It focusses on an approach followed in the rewriting community to formalize the concept of strategy. Based on rewriting concepts, several definitions of strategy are reviewed and connected: in order to catch the higher-order nature of strategies, a strategy is defined as a proof term expressed in the rewriting logic or in the rewriting calculus; to address in a coherent way deduction and computation, a strategy is seen as a subset of derivations; and to recover the definition of strategy in sequential path-building games or in functional programs, a strategy is considered as a partial function that associates to a reduction-in-progress, the possible next steps in the reduction sequence.