Abstract
This paper 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 paper presents such definitions and some fundamental theorems, together with brief remarks on applications to record handling, evaluation of recursively defined functions, and control flow analysis for optimizing compilers.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M.A. Arbib and E.G. Manes, Arrows, Structures, and Functors, Academic Press, New York, 1975.
E.F. Codd, A relational model of data for large shared data banks, Comm. ACM, 13 (1970), pp. 377–387.
H. Ehrig, P. Padawitz, and B.K. Rosen, Rapid evaluation of recursively defined functions, in preparation.
H. Ehrig, M. Pfender, and H.J. Schneider, Graph grammars: an algebraic approach, Proc. 14th Ann. IEEE Symp. on Switching and Automata Theory, Iowa City, October 1973, pp. 167–180.
H. Ehrig and B.K. Rosen, The mathematics of record handling, Lecture Notes in Computer Sci. 52 (1977), pp. 206–220.
H. Ehrig and K.W. Tischer, Graph grammars and applications to specialization and evolution in biology, J. Computer and System Sci., 11 (1975), pp. 212–236.
R. Farrow, K. Kennedy, and L. Zucconi, Graph grammars and global program data flow analysis, Proc. 17th Ann. IEEE Symp. on Foundations of Computer Sci., Houston, October 1976, pp. 42–56.
H. Herrlich and G. Strecker, Category Theory, Allyn and Bacon, Rockleigh, New Jersey, 1973.
H.-J. Kreowski, Ein Pumpinglemma für Kanten-Kontextfreie Graph-Sprachen, Bericht 77-15, Fachbereich Informatik, Tech. U. Berlin, September 1977.
M.J. O'Donnell, Computing in systems described by equations, Lecture Notes in Computer Science, 58 (1977).
G. Pacini, C. Montangero, and F. Turini, Graph representation and computation rule for typeless recursive languages, Lecture Notes in Computer Science, 14 (1974), pp. 157–169.
V. Rajlich, Dynamics of discrete systems..., J. Computer and System Sci., 11 (1975), pp. 186–202.
B.K. Rosen, Deriving graphs from graphs by applying a production, Acta Informatica, 4 (1975), pp. 337–357.
H.J. Schneider and H. Ehrig, Grammars on partial graphs, Acta Informatica, 6 (1976), pp. 297–316.
J. Vuillemin, Correct and optimal implementations of recursion in a simple programming language, J. Computer and System Sci., 9 (1974), pp. 332–354.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1978 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ehrig, H., Kreowski, HJ., Maggiolo-Schettini, A., Rosen, B.K., Winkowski, J. (1978). Deriving structures from structures. In: Winkowski, J. (eds) Mathematical Foundations of Computer Science 1978. MFCS 1978. Lecture Notes in Computer Science, vol 64. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08921-7_66
Download citation
DOI: https://doi.org/10.1007/3-540-08921-7_66
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08921-6
Online ISBN: 978-3-540-35757-5
eBook Packages: Springer Book Archive