Abstract Rewriting System (ARS)

An Abstract Rewriting System (ARS) is a mathematical structure used to study the process and properties of rewriting systems.

• Context:
  • It can (typically) be defined as a set of objects along with a Binary Relation that describes how one object can be transformed into another within the system.
  • It can range from simple systems with basic rewriting rules to complex systems that include labeled or indexed rules to enhance the expressiveness or control the application of rules.
  • It can help explore properties such as Confluence and Termination (which determine the overall behavior and reliability of the rewriting processes).
  • ...
• Example(s):
  • a String Rewriting System, where objects are strings, and the relations are defined by the rewriting rules applicable to these strings.
  • a Graph Rewriting System that illustrates how structures such as graphs can be transformed by applying local or global rewriting rules.
  • ...
• Counter-Example(s):
  • State Machines, which typically do not involve the concept of rewriting but instead transition between states based on input.
  • ...
• See: Mathematical Logic, Theoretical Computer Science, Formalism (Mathematics), Rewriting, Normal Form (Abstract Rewriting), Termination (Term Rewriting), Confluence (Abstract Rewriting).

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/abstract_rewriting_system Retrieved:2017-5-18.
  • 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 [math]\displaystyle{ \rightarrow }[/math] ; 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).

---