Contents

# Contents

## Idea

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”.

## Definition

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.

## References

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