nLab abstract rewriting system




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,)(X, \rightarrow) is given by a set XX and a binary relation \rightarrow on XX, ie. a subset of the cartesian product X×XX \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 xx 1x 2x \to x_1 \to x_2 \to \cdots (thought of as successive stages of rewriting xx), for instance to see if they are confluent.


Last revised on November 25, 2022 at 06:03:34. See the history of this page for a list of all contributions to it.