English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Modular Proofs for Completeness of hierarchical term rewriting systems

Krishna Rao, M. R. K. (1995). Modular Proofs for Completeness of hierarchical term rewriting systems. Theoretical Computer Science, 151(2), 487-512.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Krishna Rao, M. R. K.1, Author           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: In this paper, we study modular aspects of hierarchical combinations of term rewriting systems. System $\R_0 \cup \R_1$ is a hierarchical combination if the defined symbols of two subsystems, $\R_0$ and $\R_1$ are disjoint, some of the defined symbols of $\R_0$ are constructors in $\R_1$ and the defined symbols of $\R_1$ do not occur in $\R_0$. It is shown that in hierarchical combinations, a reduction can increase the rank of a term. Therefore, techniques employed in proving modularity results for direct sums and constructor sharing systems are not applicable for hierarchical combinations. We propose a set of sufficient conditions for modularity of completeness of hierarchical combinations. The sufficient conditions are syntactic ones (about recursion) based on constructor discipline. We prove our result by showing that hierarchical combination $\R_0 \cup \R_1$ satisfying our sufficient conditions is innermost normalizing and locally confluent, if $\R_0$ and $\R_1$ are complete constructor systems. The result generalizes Middeldorp and Toyama's result on modularity of completeness for shared constructor systems.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-121995
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 519488
Other: Local-ID: C1256104005ECAFC-2E95B8080DC56906C12562E0003A03F5-KrishnaRaoTCS
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Theoretical Computer Science
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 151 (2) Sequence Number: - Start / End Page: 487 - 512 Identifier: ISSN: 0304-3975