Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Krishna Rao, M. R. K.dblp

BibTeX cite key*:

KrishnaRaoTCS

Title

Title*:

Modular Proofs for Completeness of hierarchical term rewriting systems

Journal

Journal Title*:

Theoretical Computer Science
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

North-Holland Publishing Co.
Publisher's URL:


Publisher's
Address:


ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

151
Number:

2

Publishing Date:

December 1995

Pages*:

487-512
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

term rewriting, modularity

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:
MPG publications list, university publications list


BibTeX Entry:
@ARTICLE{KrishnaRaoTCS,
AUTHOR = {Krishna Rao, M. R. K.},
 TITLE = {Modular Proofs for Completeness of hierarchical term rewriting systems},
 JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {North-Holland Publishing Co.},
 YEAR = {1995},
 NUMBER = {2},
 VOLUME = {151},
 PAGES = {487--512},
 MONTH = {December},
 ISBN = {0304-3975},
}

Entry last modified by Uwe Brahm, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
M. R. K. Krishna Rao		Created
03/01/1996 11:33:41 AM
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Uwe Brahm/MPII/DE
M. R. K. Krishna Rao/AG2/MPII/DE
M. R. K. Krishna Rao/AG2/MPII/DE
M. R. K. Krishna Rao/AG2/MPII/DE		Edit Dates
20.01.97 01:25:44
20.03.96 17:59:51
01/03/96 14:08:02
01/03/96 12:48:08
01/03/96 12:40:19