Abstract
Hyperedge replacement systems are introduced as a device for generating hypergraph languages including graph languages and string languages (where the strings are uniquely represented as certain graphs). Our concept combines a context-free type of rewriting with a comparatively large generative power. The former is indicated, for example, by a pumping lemma, the latter by the examples (among them you find the refinement of Petri nets, the analysis of flow diagrams, the structural description of molecules and some typical non-context-free string languages).
Preview
Unable to display preview. Download preview PDF.
References
M. Bauderon, B. Courcelle: Graph Expressions and Graph Rewriting, Comp. Sci. Research Report no. 8525, University of Bordeaux (1985)
C. Batini, A. D'Atri: Schema Hypergraphs: A Formalism to Investigate Logical Data Base Design, Lect. Not. Comp. Sci. 100, 177–194 (1981)
C. Berge: Graphs and Hypergraphs, North-Holland (1973)
I. Castellani, U. Montanari: Graph Grammars for Distributed Systems, Lect. Not. Comp. Sci. 153 (1983), 20–38
V. Claus, H. Ehrig, G. Rozenberg (eds.): Graph-Grammars and Their Application to Computer Science and Biology, Lect. Not. Comp. Sci. 73 (1979)
H. Ehrig: Introduction to the Algebraic Theory of Graph Grammars, Lect. Not. Comp. Sci. 73, 1–19 (1979)
H. Ehrig, A. Habel, B.K. Rosen: Rosen: Concurrent Transformations of Relational Structures, Fundamenta Informaticae IX 13–50 (1986)
H. Ehrig, H.-J. Kreowski, A. Maggiolo-Schettini, B.K. Rosen, and J. Winkowski: Transformations of Structures: An Algebraic Approach, Math. Syst. Theory 14, 305–334 (1981)
H. Ehrig, M. Nagl, G. Rozenberg (eds.): Graph-Grammars and Their Application to Computer Science, 2nd Int. Workshop on Graph Grammars and Their Application to Computer Science, Lect. Not. Comp. Sci. 153 (1983)
R. Farrow, K. Kennedy, L. Zucconi: Graph Grammars and Global Program Data Flow Analysis, Proc. 17th Ann. IEEE Symp. on Found. of Comp. Sci., Houston, Texas, Oct. 1976, 42–56
J. Feder: Plex Languages, Inform. Sci. 3 (1971), 225–241
A. Habel, H.-J. Kreowski: On Context-Free Graph Languages Generated by Edge Replacement, LNCS 153, 143–158 (1983)
—: Characteristics of Graph Languages Generated by Edge Replacement, University of Bremen, Comp. Sci. Report No. 3/85 (1985), to appear in Theor. Comp. Sci.
J.E. Hopcroft, J.D. Ullman: Formal Languages and Their Relation to Automata, Addison-Wesley 1969
D. Janssens, G. Rozenberg: On the Structure of Node-Label-Controlled Graph Grammars, Information Science 20, 191–216 (1980)
H.-J. Kreowski: Manipulationen von Graphmanipulationen, Ph. D. Thesis, Techn. Univ. Berlin, Comp. Sci. Dept., 1977
—: A Pumping Lemma for Context-Free Graph Languages, LNCS 73, 270–283 (1979)
U. Lichtblau: Decompilation of Control Structures by Means of Graph Transformations, LNCS 185, 284–297 (1985)
M. Nagl: A Tutorial and Bibliographical Survey on Graph Grammars, LNCS 73, 70–126 (1979)
T. Pavlidis: Linear and Context-Free Graph Grammars, Journ. ACM 19, 1, 11–23 (1972)
V. Rajlich: Dynamics of Discrete Systems and Pattern Reproduction, Journ. Comp. Syst. Sci. 11, 186–202 (1975)
H. Schmeck: Flow Graph Grammars and Flow Graph Languages, in M. Nagl, J. Perl (eds.): Graphtheoretic Concepts in Computer Science, Proc. of the WG' 83, 319–329 (1983)
I. Suzuki, T. Murata: Stepwise Refinements of Transitions and Places, Informatik-Fachberichte 52, Springer, 136–141 (1980)
R. Valette: Analysis of Petri Nets by Stepwise Refinements, Journ. Comp. Syst. Sci. 18, 35–46 (1979)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Habel, A., Kreowski, HJ. (1987). Some structural aspects of hypergraph languages generated by hyperedge replacement. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds) STACS 87. STACS 1987. Lecture Notes in Computer Science, vol 247. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0039608
Download citation
DOI: https://doi.org/10.1007/BFb0039608
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17219-2
Online ISBN: 978-3-540-47419-7
eBook Packages: Springer Book Archive