Termination of String Rewriting Rules that have One Pair of Overlaps

Abstract

This paper presents a partial solution to the long standing open problem of termination of one-rule string rewriting. Overlaps between the two sides of the rule play a central rule in existing termination criteria. We characterize termination of all one-rule string rewriting systems that have one such overlap at either end. This both completes a result of Kurth and generalizes a result of Shikishima-Tsuji et al.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 2002
Accession Number
ADA408928

Entities

People

  • Alfons Geser

Tags

Communities of Interest

  • Space

DTIC Thesaurus Topics

  • Abstracts
  • Aeronautics
  • Alphabets
  • Classification
  • Contractors
  • Contracts
  • Databases
  • Electronic Mail
  • Equations
  • Language
  • Language Translation
  • Security
  • Sequences
  • Space Sciences
  • Standards
  • Symposia
  • Virginia

Readers

  • Computer Programming and Software Development.
  • Electrical Engineering