Abstract
The work reported here is part of the PROGRES (PROgrammed Graph Rewriting Systems) project. PROGRES is a very high level multi paradigm language for the specification of complex structured data types and their operations. The data structures are modelled as directed, attributed, node and edge labeled graphs (diane graphs). The basic programming constructs of PROGRES are graph rewriting rales (productions and tests) and derived relations on nodes (paths and restrictions).
Although graph rewriting systems have successfully been used for specification purposes in many application areas since about 20 years, there was no sufficient tool available for the execution and implementation of graph grammar specifications. Especially, the problem of efficiently searching for a redex for an arbitrary given rewrite rale has been unsolved for a long time. In this paper we propose a new, heuristic, graph based algorithm solving this graph pattern matching problem. This algorithm has been implemented and is used successfully within the PROGRES environment.
Supported by Deutsche Forschungsgemeinschaft.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beyer M.: GAG: Ein graphischer Editor für algebraische Graphgrammatiksysteme; Masters Thesis, TU Berlin (1991)
Bunke H., Glauser T., Tran T.-H.: An efficient implementation of graph grammars based on the RETE matching algorithm; in, 174–189 (1991)
Dörr H.: Bypass Strong V-Structures and Find an Isomorphic Labelled Subgraph in Linear Time; technical report, Report B-94-08, Freie Universität Berlin (1994)
Ehrig H., Kreowski H.-J., Rozenberg G. (Eds.): Proc. 4th Int. Workshop on Graph-Grammars and their Application to Computer Science; LNCS 532, Berlin, Springer-Verlag (1991)
Engels G., Lewerentz C, Nagl M., Schäfer W., Schürr A.: Experiences in Building Integrated Tools, Part I: Tool Specification; in ACM Transactions on Software Engineering and Methodology, Vol.1, No.2, 135–167, ACM Press (1992)
Göttler H.: Graph-Grammatiken in der Softwaretechnik; IFB 178, Springer-Verlag (1988)
Gould R.: GRAPH THEORY; The Benjamin Cummings Publishing Company, Menlo Park, California (1988)
Haralick R. M., Elliot G. L.: Increasing Tree Search Efficiency for Constraint Satisfaction Problems; in Artificial Intelligence, Vol.14, 263–313 (1980)
Van Hentenryck P.: Constraint Satisfaction in Logic Programming; MIT Press, London (1989)
Lee H.-Y., Reid Th. F., Jarzabek St. (Eds): CASE '93 Proc. 6th Int. Workshop on Computer-Aided Software Engineering; IEEE Computer Society Press (1993)
Kiesel N., Schürr A., Westfechtel B.: Design and Evaluation of GRAS, a Graph-Oriented Database System for Engineering Applications; in [LeReJa 93], 272–286 (1992)
Schmidt G., Berghammer R. (Eds.): Graph-Theoretic Concepts in Computer Science; WG '91, LNCS 570, Berlin, Springer-Verlag (1992)
Schürr A.: Operationales Spezifizieren mit programmierten Graphersetzungssystemen; PhD. Thesis, RWTH Aachen, Wiesbaden, Deutscher Universitäts-Verlag (1991)
Schurr A.: PROGRESS: A VHL-Language Based on Graph Grammars; in, 641–659 (1991)
Zündorf A.: Implementation of the imperative / rule based language PROGRES; technical report, AIB 92-38, RWTH Aachen (1992)
Zündorf A.: A Heuristic for the Subgraph Isomorphism Problem in Executing PROGRES; technical report, AIB 93-5, RWTH Aachen (1993)
Zündorf A., Schürr A.: Nondeterministic Control Structures for Graph Rewriting Systems; in, 48–62 (1992)
Zündorf A.: PROgrammierte GRaphErsetzungsSysteme — Spezifikation, Implementierung und Anwendung einer integrierten Entwicklungsumgebung; PhD Thesis, RWTH Aachen (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zündorf, A. (1996). Graph pattern matching in PROGRES. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds) Graph Grammars and Their Application to Computer Science. Graph Grammars 1994. Lecture Notes in Computer Science, vol 1073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61228-9_105
Download citation
DOI: https://doi.org/10.1007/3-540-61228-9_105
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61228-5
Online ISBN: 978-3-540-68388-9
eBook Packages: Springer Book Archive