Abstract
In this paper, we introduce and study a rendezvous mechanism for parallel replacements of hyperedges by (hyperedge-decorated) graphs that allows some merging of the replacing graphs if the attachment of the replaced hyperedges shares some nodes. The main result shows that the rendezvous mechanism can increase the generative power of table-controlled parallel hyperedge replacement graph grammars (which themselves are more powerful than ordinary hyperedge replacement graph grammars).
The author thanks ÖSW, Bochum for its financial support which made his stay in Bremen possible.
Partially supported by the ESPRIT Basic Research WG 3299 (COMPUGRAPH).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bauderon, B. Courcelle. Graph Expressions and Graph Rewriting. Mathematical Systems Theory, 20, 83–127, 1987.
D. Bailey, J. Cuny, C. Fischer. Programming with Very Large Graphs. Lecture Notes in Computer Science, volume 532, 84–97, 1991.
P. Boehm, H.-R. Fonio, A. Habel. Amalgamation of Graph Transformations: A Synchronization Mechanism. Journal of Computer and System Sciences, 34, 377–408, 1987.
B. Courcelle. An Axiomatic Definition of Context-Free Rewriting and its Application to NLC Graph Grammars. Theoretical Computer Science, 55, 141–1812, 1987.
P. Degano, U. Montanari. A Model of Distributed Systems based on Graph Rewriting. Journ. ACM, 34, 411–449, 1987.
H. Ehrig, H.-J. Kreowski. Parallel Graph Grammars. In A. Lindenmayer, G. Rozenberg, editors, Automata, Languages, Development, 425–442. North Holland, Amsterdam, 1976.
H. Ehig, G. Taentzer. From Parallel Graph Grammars to Parallel High-Level Replacement Systems. In G. Rozenberg, A. Salomaa, editors, Lindenmayer Systems, 283–304. Springer, 1992.
J. Feder. Plex Languages. Inform. Sci., 3, 225–241, 1971.
A. Habel. Hypcredge Replacement: Grammars and Languages. PhD thesis, Bremen, 1989.
A. Habel, H.-J. Kreowski. Some Structural Aspects of Hypergraph Languages Generated by Hypcredge Replacement. Lecture Notes in Computer Science, volume 247, 207–219, 1987.
A. Habel, H.-J. Kreowski, W. Vogler. Metatheorems for Decision Problems on Hyperedge Replacement Graph Languages. Acta Infonnatica, 26, 657–677, 1989.
G.T. Herman, G Rozenberg. Developmental Systems and Languages. North Holland/American Elsevier, New York, 1975.
H.-J. Kreowski. Is Parallelism Already Concurrency? Part 1: Derivations in Graph Grammars. Lecture Notes in Computer Science, volume 291, 343–360, 1987.
H.-J. Kreowski. Parallel Hyperedge Replacement. In G. Rozenberg, A. Salomaa, editors, Lindenmayer Systems, 271–282. Springer, 1992.
T. Lengauer, E. Wanke. Efficient Analysis of Graph Properties on Context-Free Graph Languages. Lecture Notes in Computer Science, volume 317, 379–393, 1988.
M. Nagl. Set Theoretic Approaches to Graph Grammars. Lecture Notes in Computer Science, volume 291, 41–54, 1987.
T. Pavlidis. Linear and Context-Free Graph Grammars. Journ. ACM, 19(1), 11–23, 1972.
G. Rozenberg, A. Salomaa. The Mathematical Theory of L Systems. Academic Press, New York, 1980.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
David, G., Drewes, F., Kreowski, HJ. (1993). Hyperedge replacement with rendezvous. In: Gaudel, M.C., Jouannaud, J.P. (eds) TAPSOFT'93: Theory and Practice of Software Development. CAAP 1993. Lecture Notes in Computer Science, vol 668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56610-4_63
Download citation
DOI: https://doi.org/10.1007/3-540-56610-4_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56610-6
Online ISBN: 978-3-540-47598-9
eBook Packages: Springer Book Archive