Browse Prior Art Database

Commutativity of Independent Transformations on Complex Objects

IP.com Disclosure Number: IPCOM000148735D
Original Publication Date: 1976-Oct-19
Included in the Prior Art Database: 2007-Mar-30
Document File: 54 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Ehrig, Hartmut: AUTHOR [+3]

Abstract

Hartrnut Ehrigt and Barry K. Rosen Computer Sciences DepartmentIBM Thomas J. Watson Research Center Yorktown Heights, New York 10598 ABSTRACT: In a system of complex objects and transformation rules it is often important to show that the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. Theorems establishing such behavior have been called Church-Rosser theorems. One elementary but useful Church-Rosser theorem in formal language theory is the fact that nonoverlapping applications of productions commute. Our commutativity theorem extends this fact to systems where objects are arbitrarily complex directed graphs with arbitrarily complex packets of information assigned to nodes and arcs. The proper formulation of the theorem at this level of generality requires that some overlapping be permitted in the hypothesis. Examples of the theorem's use are presented. One of these is part of the mathematical basis for the recently proposed "delay rule" or "lazy evaluation" method for evaluating recursively defined functions.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 54

RC 6251 (#26882) 10/19/76 Computer Science 52 pages

Commutativity of Independent Transformations on Complex Objects

Hartrnut Ehrigt and Barry K. Rosen

Computer Sciences Department
IBM Thomas J. Watson Research Center Yorktown Heights, New York 10598

ABSTRACT: In a system of complex objects and transformation rules it is often important to show that the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. Theorems establishing such behavior have been called Church-Rosser theorems.

   One elementary but useful Church-Rosser theorem in formal language theory is the fact that nonoverlapping applications of productions commute. Our commutativity theorem extends this fact to systems where objects are arbitrarily complex directed graphs with arbitrarily complex packets of information assigned to nodes and arcs. The proper formulation of the theorem at this level of generality requires that some overlapping be permitted in the hypothesis. Examples of the theorem's use are presented. One of these is part of the mathematical basis for the recently proposed "delay rule" or "lazy evaluation" method for evaluating recursively defined functions.

   The argument is presented within the algebraic theory of graph grammars (originated by Ehrig, Pfender, and Schneider and subsequently modified and generalized by several researchers). In addition to the commutativity theorem, this paper shows how to eliminate some technical complications in the theory.

tFachbereich Kybernetik, Technische Universitiit,

1 Berlin 10, Federal Republic of Germany

[This page contains 1 picture or other non-text object]

Page 2 of 54

LIAIITED DISTRIBUTION NOTICE


This report has been submitted for publication elsewhere and has been issued as a Research Report for early dissemination of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:
IBhl Thomas j. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 54

1. INTRODUCTION

Many computing problems can be usefully described in terms of applying "rules" or

"transformations" or "productions" to complex objects such as strings, trees, graphs, state vectors,

and files. It sometimes happens that an object 5 can be transformed into two different objects q

and q#, depending on which production is applied next and where in 5 it is applied. Yet the choice

between 7 and 17#

may be inconsequential: the fully transformed objects derivable from 7 may be

equivalent to those derivable from q# for the matter at hand. Theorems to the effect that certain

systems of objects and productions are well behaved in this respect have been called

Church-Rosser theorems [21]....