Rewriting

For other uses, see Rewriting (disambiguation).

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines,[1][2] or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

Rewriting can be non-deterministic. One rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications. When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several theorem provers[3] and declarative programming languages are based on term rewriting.[4][5]

  1. ^ Joseph Goguen "Proving and Rewriting" International Conference on Algebraic and Logic Programming, 1990 Nancy, France pp 1-24
  2. ^ Sculthorpe, Neil; Frisby, Nicolas; Gill, Andy (2014). "The Kansas University rewrite engine" (PDF). Journal of Functional Programming. 24 (4): 434–473. doi:10.1017/S0956796814000185. ISSN 0956-7968. S2CID 16807490. Archived (PDF) from the original on 2017-09-22. Retrieved 2019-02-12.
  3. ^ Hsiang, Jieh; Kirchner, Hélène; Lescanne, Pierre; Rusinowitch, Michaël (1992). "The term rewriting approach to automated theorem proving". The Journal of Logic Programming. 14 (1–2): 71–99. doi:10.1016/0743-1066(92)90047-7.
  4. ^ Frühwirth, Thom (1998). "Theory and practice of constraint handling rules". The Journal of Logic Programming. 37 (1–3): 95–138. doi:10.1016/S0743-1066(98)10005-5.
  5. ^ Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Quesada, J.F. (2002). "Maude: Specification and programming in rewriting logic". Theoretical Computer Science. 285 (2): 187–243. doi:10.1016/S0304-3975(01)00359-0.