Editing Rewriting (section)

{{Short description|Replacing subterm in a formula with another term}}
{{other uses}}

In [[mathematics]], [[computer science]], and [[logic]], '''rewriting''' covers a wide range of methods of replacing subterms of a [[well-formed formula|formula]] with other terms. Such methods may be achieved by '''rewriting systems''' (also known as '''rewrite systems''', '''rewrite engines''',<ref>
[[Joseph Goguen]] "Proving and Rewriting" International Conference on Algebraic and Logic Programming, 1990 Nancy, France pp 1-24</ref><ref name="SculthorpeFrisby2014">{{cite journal |last1=Sculthorpe |first1=Neil |last2=Frisby |first2=Nicolas |last3=Gill |first3=Andy |title=The Kansas University rewrite engine |journal=[[Journal of Functional Programming]] |volume=24 |issue=4 |year=2014 |pages=434–473 |issn=0956-7968 |doi=10.1017/S0956796814000185 |s2cid=16807490 |url=http://irep.ntu.ac.uk/id/eprint/27901/1/PubSub5454_Sculthorpe.pdf |access-date=2019-02-12 |archive-date=2017-09-22 |archive-url=https://web.archive.org/web/20170922234803/http://irep.ntu.ac.uk/id/eprint/27901/1/PubSub5454_Sculthorpe.pdf |url-status=live }}</ref> or '''reduction systems'''). In their most basic form, they consist of a set of objects, plus [[Relation (mathematics)|relations]] on how to transform those objects.

Rewriting can be [[non-deterministic algorithm|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 program]]s, and several [[automated theorem proving|theorem prover]]s<ref>{{cite journal|doi=10.1016/0743-1066(92)90047-7|title=The term rewriting approach to automated theorem proving|journal=The Journal of Logic Programming|volume=14|issue=1–2|pages=71–99|year=1992|last1=Hsiang|first1=Jieh|last2=Kirchner|first2=Hélène|last3=Lescanne|first3=Pierre|last4=Rusinowitch|first4=Michaël|doi-access=free}}</ref> and [[declarative programming language]]s are based on term rewriting.<ref>{{cite journal|doi=10.1016/S0743-1066(98)10005-5 |title=Theory and practice of constraint handling rules |journal=The Journal of Logic Programming |volume=37 |issue=1–3 |pages=95–138 |year=1998 |last1=Frühwirth |first1=Thom |doi-access=free }}</ref><ref name="Clavel.Duran.Eker.2002">{{Cite journal | doi=10.1016/S0304-3975(01)00359-0| title=Maude: Specification and programming in rewriting logic| journal=Theoretical Computer Science| volume=285| issue=2| pages=187–243| year=2002| last1=Clavel| first1=M.| last2=Durán| first2=F.| last3=Eker| first3=S.| last4=Lincoln| first4=P.| last5=Martí-Oliet| first5=N.| last6=Meseguer| first6=J.| last7=Quesada| first7=J.F.| doi-access=free}}</ref>