Abstract
This paper illustrates a categorical approach to the theory of rewriting systems along the lines adumbrated by Buchberger [3] It shows how 2-categories
provide a simple framework for string rewriting systems and briefly reviews
the theory of string rewriting to indicate its simplicity. In contrast the theory
of term rewriting systems is complicated by the interaction of substitution
and rewriting. We outline a 3-categorical framework for linear term rewriting systems and show by a detailed example how this separates substitution
and rewriting and reduces linear term rewriting to the simplicity of string
rewriting, but with one extra dimension.
provide a simple framework for string rewriting systems and briefly reviews
the theory of string rewriting to indicate its simplicity. In contrast the theory
of term rewriting systems is complicated by the interaction of substitution
and rewriting. We outline a 3-categorical framework for linear term rewriting systems and show by a detailed example how this separates substitution
and rewriting and reduces linear term rewriting to the simplicity of string
rewriting, but with one extra dimension.
| Original language | English |
|---|---|
| Title of host publication | The Unified Computation Laboratory |
| Subtitle of host publication | Modelling, Specifications, and Tools |
| Editors | Charles Rattray, Robert G. Clark |
| Place of Publication | Oxford |
| Publisher | Oxford University Press |
| Pages | 101-110 |
| Number of pages | 10 |
| ISBN (Print) | 0198536844, 9780198536840 |
| Publication status | Published - 1992 |