Abstract
Basing on the Church-Rosser Theorems in /EK 76b/ analysis and synthesis of parallel derivations in graph grammars are introduced. This allows specific, transparent transformations of derivation sequences, which can be used as elementary steps of algorithms acting on derivations, and the calculation rules for transformations presented in this paper are needed to prove the correctness of such algorithms. One example of this kind is given: the equivalence of derivations in graph grammars is defined and canonical derivations representing the equivalence classes are specified. For graph grammars canonical derivations will be as important as leftmost derivations and respective concepts for classical Chomsky grammars to the design of correct parsing algorithms.
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
Ehrig, H.: Embedding Theorems in the Algebraic Theory of Graph Grammars, this volume
Ehrig, H., Kreowski, H.-J.: Categorical Approach to Graphic Systems and Graph Grammars, Conf. Report Algebraic System Theory, Udine 1975, Springer Lect. Notes in Econ. Math. Syst. 131 (1976), 323–351
Ehrig, H., Kreowski, H.-J.: Parallelism of Manipulations in Multidimensional Information Structures, Proc. Conf. Math. Foundations of Comp. Sci., Gdańsk 1976, Springer Lect. Notes in Comp. Sci. 45 (1976), 284–293
Ehrig, H., Pfender, M., Schneider, H.J.: GRAPH GRAMMARS: An Algebraic Approach, Proc. IEEE Conf. on Automata and Switching Theory, Iowa City 1973, 167–180
Ehrig, H., Rosen, B.K.: Commutativity of Independent Transformations on Complex Objects, IBM Research Report, RC 6251, Oct 1976
Ehrig, H., Rosen, B.K.: The Mathematics of Record Handling (in preparation)
Farrow, R., Kennedy, K., Zucconi, L.: Graph Grammars and Global Program Data Flow Analysis, Proc. 17th Ann. IEEE Symp. on Foundations of Comp. Sci., Houston, 1976
Franck, R.: PLAN2D — Syntaxanalyse von Präzedenz-Graph-Grammatiken, Dissertation, Technische Universität Berlin, FB 20, 1975
Griffiths, T.V.: Some Remarks on Derivations in General Rewriting Systems, Information and Control 12, 1968, 27–54
Kreowski, H.-J.: Kanonische Ableitungssequenzen für Graph-Grammatiken, Research Report, FB 20, Techn. Univ. Berlin, 76-26
Rosen, B.K.: Tree-Manipulating System and Church-Rosser Theorems, Journ. ACM 20, 1, 1973, 160–187
—: Correctness of Parallel Programs: The Church-Rosser Approach, Theoretical Comp. Sci. 2, 1976, 183–207
— A Church-Rosser Theorem for Graph-Grammars (announcement), STGACT News 7, 3, 1975, 26–31
—: Deriving Graphs from Graphs by Applying a Production, Acta Informatica 4, 1975, 337–357
Schneider, H.J.: Conceptual Data Base Description Using Graph Grammars, to appear in: Proc. Workshop "Graphentheoretische Konzepte in der Informatik", Göttingen, 1976
Sethi, R.: Testing for the Church-Rosser Property, Journ. ACM 21, 4, 1974, 671–679
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kreowski, HJ. (1977). Transformations of derivation sequences in graph grammars. In: Karpiński, M. (eds) Fundamentals of Computation Theory. FCT 1977. Lecture Notes in Computer Science, vol 56. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08442-8_94
Download citation
DOI: https://doi.org/10.1007/3-540-08442-8_94
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08442-6
Online ISBN: 978-3-540-37084-0
eBook Packages: Springer Book Archive