Difference between revisions of "Abstract rewriting system"
Karl Jones (Talk | contribs) (Created page with "In mathematical logic and theoretical computer science, an '''abstract rewriting system''' (also (abstract) reduction system or abstract rewrite system; abbreviation A...") |
(No difference)
|
Latest revision as of 11:17, 9 September 2016
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of rewriting systems.
In its simplest form, an ARS is simply a set (of "objects") together with a binary relation, traditionally denoted with ->; this definition can be further refined if we index (label) subsets of the binary relation.
Despite its simplicity, an ARS is sufficient to describe important properties of rewriting systems like normal forms, termination, and various notions of confluence.
Historically, there have been several formalizations of rewriting in an abstract setting, each with its idiosyncrasies. This is due in part to the fact that some notions are equivalent, see below in this article. The formalization that is most commonly encountered in monographs and textbooks, and which is generally followed here, is due to Gérard Huet (1980).
See also
External links
- Abstract rewriting system @ Wikipedia
