Browse Prior Art Database

Transformations of Structures: an Algebraic Approach

IP.com Disclosure Number: IPCOM000148827D
Original Publication Date: 1979-Dec-10
Included in the Prior Art Database: 2007-Mar-30
Document File: 42 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Ehrig, Hartmut: AUTHOR [+6]

Abstract

Hartmut Ehrig and Hans-Jorg Kreowskif' Andrea Maggiolo-Schettini* Barry K. Rosen?? Josef Winkowski*** f' Fachbereich Informatik, Technische Universitat Berlin, 1000 Berlin 10, Federal Republic of Germany Istituto di Scienze dell'Informazione, Universita di Pisa, 56100 Pisa, Italy tt Computer Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA Instytut Podstaw Informatyki PAN, 00-901 Warszawa, PKiN, Box 22, Poland Abstract: This report (which supercedes RC 7046) introduces a new mathematical approach to transformations of structures, where the concept of "structure" is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This report presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recur- sively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this report uses ideas and results from abstract algebra to minimize the need for elaborate constructions.

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 5% of the total text.

Page 1 of 42

RC 7998 (#34713) 12/10/79 Computer Science 40 pages

Transformations of Structures: an Algebraic Approach

Hartmut Ehrig and Hans-Jorg Kreowskif'

Andrea Maggiolo-Schettini* *

Barry K. Rosen??

Josef Winkowski***

f' Fachbereich Informatik, Technische Universitat Berlin,
1000 Berlin 10, Federal Republic of Germany

** Istituto di Scienze dell'Informazione, Universita di Pisa, 56100 Pisa, Italy

tt Computer Sciences Department,
IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA

*** Instytut Podstaw Informatyki PAN,
00-901 Warszawa, PKiN, Box 22, Poland

Abstract: This report (which supercedes RC 7046) introduces a new mathematical approach to transformations of structures, where the concept of "structure" is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This report presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recur- sively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this report uses ideas and results from abstract algebra to minimize the need for elaborate constructions.

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

Page 2 of 42

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

Page 3 of 42

1. Introduction

   To aid in summarizing the contents of the paper, we introduce some major concepts informal- ly. Let there be given a set whose members are called predicates and let each predicate be classified as unary or binary or ... N-ary ... . An N-ary predicate may be formally applied to any list (x,, ..., xN) of arguments having the length N. When P is applied to (x,, ..., xN), the formula P(xl, ..., xN) results. Here the similarity to mathematical logic ends: we are unconcerned about truth and only marginally concerned about consistency of sets of formulas. Instead, a set of formulas is a very high level representation of the world as modelled by a computer program, be it a program to maintain a data base or to simulate traffic flow or to control machines that assemble carburators. Programs that change their models are of special concern. Any set of formulas will be called a structure. Only a relatively small set of structures can arise from the behavior of any one program. For example, a relational data base [Co70, Sec. 1.31 is a structure with an N-ary predicate for each N-column relation. For each row in relation P we have a formula P(x...