The notion of abstract rewriting system is the simplest mathematical formalization of what is a rewriting system. It doesn’t presuppose anything on the nature of the syntactical objects which are rewritten, thus the word “abstract”.
An abstract rewriting system $(X, \rightarrow)$ is given by a set $X$ and a binary relation $\rightarrow$ on $X$, ie. a subset of the cartesian product $X \times X$.
So this is a concept with an attitude: While an abstract re-writing system is just a relation, calling this relation an abstract rewriting system indicates that one is interested in studying the behaviour of chains of related elements $x \to x_1 \to x_2 \to \cdots$ (thought of as successive stages of rewriting $x$), for instance to see if they are confluent.
Wikipedia, Abstract rewriting system
Wikipedia, Confluence_(abstract_rewriting)
Last revised on November 25, 2022 at 06:03:34. See the history of this page for a list of all contributions to it.