Metraipolis › archive › dc_e8aaa048d577

Abstract rewriting system — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Abstract_rewriting_system
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-07T08:36:27.860Z
SHA-256 of the archived text: 45f0eb57a56d6047df11819e858e8a953356827bc32f24025beb244902421d34
Stable URL of this page: https://metraipolis.com/documento/dc_e8aaa048d577

How to cite

Abstract rewriting system — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Abstract_rewriting_system (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e8aaa048d577 (Metraipolis archive dc_e8aaa048d577, sha256 45f0eb57a56d6047df11819e858e8a953356827bc32f24025beb244902421d34)

BibTeX

@misc{dce8aaa048d577,
  title = {Abstract rewriting system — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Abstract_rewriting_system},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e8aaa048d577; sha256 45f0eb57a56d6047df11819e858e8a953356827bc32f24025beb244902421d34},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Abstract_rewriting_system. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated 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 → {\displaystyle \rightarrow } ; 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).

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «Abstract rewriting system» — https://en.wikipedia.org/wiki/Abstract_rewriting_system
Wikidata Q2136420: «formal system for transcribing expressions into equivalent terms» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2136420
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Abstract_rewriting_system?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378824802, consultata il 2026-11-07T08:32:12.427Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c89f56e514c5f013e7de40e394ada4376e872466701e201fb08051276793ef91