Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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