Information Services banner Edinburgh Research Archive The University of Edinburgh crest

Edinburgh Research Archive >
Informatics, School of >
Informatics thesis and dissertation collection >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1842/388

This item has been viewed 10 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
ECS-LFCS-98-396.dviLaTeX DVI File790.73 kBTeX dviView/Open
ECS-LFCS-98-396.pdfAdobe PDF1.83 MBAdobe PDFView/Open
ECS-LFCS-98-396.psPostScript File1.46 MBPostscriptView/Open
Title: Categorical Term Rewriting: Monads and Modularity
Authors: Lüth , Christoph
Supervisor(s): Sannella, Donald
Kahrs, Stefan
Issue Date: Jul-1998
Publisher: University of Edinburgh. College of Science and Engineering. School of Informatics.
Abstract: Term rewriting systems are widely used throughout computer science as they provide an abstract model of computation while retaining a comparatively simple syntax and semantics. In order to reason within large term rewriting systems, structuring operations are used to build large term rewriting systems from smaller ones. Of particular interest is whether key properties are modular, that is, if the components of a structured term rewriting system satisfy a property, then does the term rewriting system as a whole? A body of literature addresses this problem, but most of the results and proofs depend on strong syntactic conditions and do not easily generalize. Although many specific modularity results are known, a coherent framework which explains the underlying principles behind these results is lacking. This thesis posits that part of the problem is the usual, concrete and syntax-oriented semantics of term rewriting systems, and that a semantics is needed which on the one hand elides unnecessary syntactic details but on the other hand still possesses enough expressive power to model the key concepts arising from the term structure, such as substitutions, layers, redexes etc. Drawing on the concepts of category theory, such a semantics is proposed, based on the concept of a monad, generalising the very elegant treatment of equational presentations in category theory. The theoretical basis of this work is the theory of enriched monads. It is shown how structuring operations are modelled on the level of monads, and that the semantics is compositional (it preserves the structuring operations). Modularity results can now be obtained directly at the level of combining monads without recourse to the syntax at all. As an application and demonstration of the usefulness of this approach, two modularity results for the disjoint union of two term rewriting systems are proven, the modularity of confluence (Toyama's theorem) and the modularity of strong normalization for a particular class of term rewriting systems (non-collapsing term rewriting systems). The proofs in the categorical setting provide a mild generalisation of these results.
Description: Laboratory for Foundations of Computer Science
Sponsor(s): DAAD (German Academic Exchange Service)
URI: http://hdl.handle.net/1842/388
Appears in Collections:Informatics thesis and dissertation collection

Items in ERA are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh 2013, and/or the original authors. Privacy and Cookies Policy