Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 DetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD0E-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD0F-E
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Krishna Rao, M. R. K.1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121995
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 519488
Anderer: Local-ID: C1256104005ECAFC-2E95B8080DC56906C12562E0003A03F5-KrishnaRaoTCS
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Theoretical Computer Science
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 151 (2) Artikelnummer: - Start- / Endseite: 487 - 512 Identifikator: ISSN: 0304-3975