Linear term rewriting systems are higher dimensional string rewriting systems

Research output: Chapter in Book/Report/Conference proceedingChapter

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.
Original languageEnglish
Title of host publicationThe Unified Computation Laboratory
Subtitle of host publicationModelling, Specifications, and Tools
EditorsCharles Rattray, Robert G. Clark
Place of PublicationOxford
PublisherOxford University Press
Pages101-110
Number of pages10
ISBN (Print)0198536844, 9780198536840
Publication statusPublished - 1992

Cite this