Logical Semantics for the Rewriting Calculus

Aaron Stump; Carsten Schürmann

doi:10.1016/j.entcs.2005.01.001

Back

Logical Semantics for the Rewriting Calculus

Journal article

Open access

Logical Semantics for the Rewriting Calculus

Aaron Stump and Carsten Schürmann

Electronic notes in theoretical computer science, Vol.125(2), pp.149-164

03/15/2005

DOI: 10.1016/j.entcs.2005.01.001

Files and links (1)

url

https://doi.org/10.1016/j.entcs.2005.01.001View

Published (Version of record) Open Access

Abstract

The Rewriting Calculus has been proposed as a language for defining term rewriting strategies. Rules are explicitly represented as terms, and are applied explicitly to other terms to transform them. Sets of rules may be applied to (sets of) terms non-deterministically to obtain sets of results. Strategies are implemented as rules which accept other rules as arguments and apply them in certain ways. This paper describes work in progress to strengthen the Rewriting Calculus by giving it a logical semantics. Such a semantics can provide crucial guidance for studying the language and increasing its expressive power. The latter is demonstrated by adding support to the Rewriting Calculus for what we call higher-form rewriting, where rules rewrite other rules. The logical semantics used is based on ordered linear logic. The paper develops the ideas through several examples.

Logical Semantics

Meta-Programming

Ordered Linear Logic

Rewriting Calculus

Details

Title: Subtitle: Logical Semantics for the Rewriting Calculus
Creators: Aaron Stump - Washington University in St. Louis
Carsten Schürmann - Yale University
Resource Type: Journal article
Publication Details: Electronic notes in theoretical computer science, Vol.125(2), pp.149-164
DOI: 10.1016/j.entcs.2005.01.001
ISSN: 1571-0661
eISSN: 1571-0661
Publisher: Elsevier B.V
Language: English
Date published: 03/15/2005
Academic Unit: Computer Science
Record Identifier: 9984259475202771

Metrics

18 Record Views