Derived Pairs, Overlap Closures, and Rewrite Dominoes: New Tools for Analyzing Term Rewriting Systems.

Abstract

Starting from the seminal work of Knuth and Bendix, we develop several notions useful in the study of term rewriting systems. In particular we introduce the notions of 'derived pairs' and 'overlap closure' and show that they are useful in analyzing sets of rewrite rules for various properties related to termination. We also introduce a new representation, based on rewrite dominoes, for rewrite rules and sequences of rewrites. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1981
Accession Number
ADA110026

Entities

People

  • David R. Musser
  • Deepak Kapur
  • John V. Guttag

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Buildings And Structures
  • Computer Science
  • Computers
  • Confluence
  • Construction
  • Contracts
  • Information Systems
  • Linear Systems
  • Mathematics
  • Military Research
  • New York
  • Program Management
  • Sequences
  • Standards
  • Technical Information Centers

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Programming and Software Development.