Graph transformation for specification and programming
Science of Computer ProgrammingPublished 1 April 1999
Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans‐Jörg Kreowski, Sabine Kuske
Citations169
SJR quartileQ3
SJR score0.43
SNIP1.23
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The concept of a transformation unit is presented, which allows systematic and structured specification and programming based on graph transformation, and a selection of applications are discussed, including the evaluation of functional expressions and the specification of an interactive graphical tool.
Abstract
The framework of graph transformation combines the potentials and advantages of both, graphs and rules, to a single computational paradigm. In this paper we present some recent developments in applying graph transformation as a rule-based framework for the specification and development of systems, languages, and tools. After reviewing the basic features of graph transformation, we discuss a selection of applications, including the evaluation of functional expressions, the specification of an interactive graphical tool, an example specification for abstract data types, and the definition of a visual database query language. The case studies indicate the need for suitable structuring principles which are independent of a particular graph transformation approach. To this end, we present the concept of a transformation unit, which allows systematic and structured specification and programming based on graph transformation.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Cambridge University Press eBooksTerm Rewriting and All That
2,116 Citations1998Franz Baader, Tobias Nipkow
Microprocessors and MicrosystemsThe implementation of functional programming languages
1,079 Citations1987
My 1987 book is now out of print, but it is available here in its entirety in PDF form, in one of two formats: single-page portrait double-page landscape and fully searchable, thanks to OCR and Norman Ramsey.
Behavioral and Brain SciencesOn artificial intelligence
885 Citations1985Peter H. Schönemann
This paper aims to boost the accuracy of a DP logistic regression (LR) via a pre-training module via a pre-training module and shows that adding a pre-training module significantly improves the accuracy of the DP-LR model.
Data Archiving and Networked Services (DANS)Term rewriting systems
780 Citations1993Jan Willem Klop
This book gives a readable but rigorous introduction to the theory of term rewriting systems, a technique used in computer science, especially functional programming, for abstract data type specification and automatic theorem-proving.
Graph-grammars: An algebraic approach
488 Citations1973Hartmut Ehrig, Michael Pfender +1 more
An algebraic theory of graph-grammars is presented using homomorphisms and pushout-constructions to specify embeddings and direct derivations constructively and allows simplification of the proofs and pregnant formulation of concepts like "parallel composition" and "translation of grammars".
Lecture notes in computer scienceIntroduction to the algebraic theory of graph grammars (a survey)
463 Citations2005Hartmut Ehrig
The aim of this survey is to motivate and introduce the basic constructions and results which have been developed in the algebraic theory of graph grammars up to now, as well as applications to a "very small data base system", where consistent states are represented as graphs.
Medical Entomology and ZoologyGraph Grammars and Their Application to Computer Science: 3rd International Workshop Warrenton, Virginia, Usa, December 2-6, 1986
391 Citations1988Hartmut Ehrig, Manfred Nagl +2 more
Lecture notes in computer scienceTerm graph rewriting
317 Citations1987Henk Barendregt, M.C.J.D. van Eekelen +4 more
Graph rewriting (also called reduction) as defined in Wadsworth [1971] was introduced in order to be able to give a more efficient implementation of functional programming languages in the form of lambda calculus or term rewrite systems.
Fundamenta InformaticaeGRAPH GRAMMARS WITH NEGATIVE APPLICATION CONDITIONS
290 Citations1996Annegret Habel, Reiko Heckel +1 more
The concept of application conditions introduced by Ehrig and Habel is restricted to contextual conditions, especially negative ones, and local confluence and the Parallelism Theorem for derivations with application conditions are state.
Lecture notes in computer scienceHyperedge Replacement: Grammars and Languages
276 Citations1992Annegret Habel
General Introduction to hyperedge-replacement grammars and basic properties of HRG's and characterizations of HRL's.
Theoretical Computer ScienceAlgebraic approach to single-pushout graph transformation
264 Citations1993M. J. S. Lowe
The whole theory for double-pushout transformations including sequential composition, parallel composition, and amalgamation can be reformulated and generalized in the new framework.
An algorithm for optimal lambda calculus reduction
252 Citations1990John Lamping
An algorithm for lambda expression reduction that avoids any copying that could later cause duplication of work and is optimal in the sense defined by Lévy is presented.
Medical Entomology and ZoologyFunctional Programming and Parallel Graph Rewriting
215 Citations1993Rinus Plasmeijer, Marko van Eekelen
This book illustrates the techniques of functional programming in Miranda and Clean, and focuses on the computational model of Graph Rewriting Systems for both sequential and parallel machines.
Fundamenta InformaticaeGRAPH PROCESSES
208 Citations1996Andrea Corradini, Ugo Montanari +1 more
A process-based semantics for graph grammars is developed, which represents each equivalence class of derivations as a graph process, which can be seen as an acyclic graph grammar, plus a mapping of its items onto the items of the given grammar.
Journal of Visual Languages & ComputingDefining and Parsing Visual Languages with Layered Graph Grammars
201 Citations1997J. Rekers, Andreas Schürr
The notion of layeredcontext-sensitive graph grammars, together with a bottom-up/top-down parsing algorithm, which can be used to generate syntax directed VL editors, which support "free editing' and parsing of their underlying graph structures.
Term Rewriting Systems
182 Citations1992Jan Willem Klop
Term graph rewriting: theory and practice
166 Citations1993M. R. Sleep, M.J. Plasmeijer +1 more
IEEE Transactions on Software EngineeringQBD*: a graphical query language with recursion
153 Citations1990Michèle Angelaccio, Tiziana Catarci +1 more
A system to query databases using diagrams as a standard user interface that makes use of a conceptual data model, a query language on this model, and a graphical user interface is proposed.
Information SciencesOn the structure of node-label-controlled graph languages
148 Citations1980D. Janssens, G. Rozenberg
The main theorem is a result on the combinatorial structure of graph languages generated by NLC grammars; it resembles the pumping theorem for context-free string languages.
Journal of Computer and System SciencesPair grammars, graph languages and string-to-graph translations
148 Citations1971Terrence W. Pratt
A pair grammar is composed of a pair of grammars whose rules and nonterminals are paired that defines a correspondence between elements of the languages defined by the two Grammars.
Electronic Notes in Theoretical Computer ScienceEnsuring Consistency of Conditional Graph Grammars - A Constructive Approach -
139 Citations1995Reiko Heckel, Annika Wagner
A general construction that transforms global consistency conditions into preconditions for individual rules is proposed that is motivated by an example specification of a safety-critical system that is, a roundabout.
Lecture notes in computer scienceGraph grammar engineering with PROGRES
132 Citations1995Andy Schürr, Andreas Winter +1 more
“Graph grammar engineering” is a first attempt to establish a new graph and rule centered methodology for the development of information system components.
Data & Knowledge EngineeringConceptual modelling of database applications using an extended ER model
108 Citations1992Gregor Engels, Martin Gogolla +5 more
This paper motivates and presents a data model for conceptual design of structural and behavioural aspects of databases using several appropriate, but yet compatible formalisms, which are integrated by a unifying common semantic.
Fundamenta InformaticaeEQUATIONAL TERM GRAPH REWRITING
97 Citations1996Zena M. Ariola, Jan Willem Klop
It is shown how Equational Logic induces a notion of copying and substitution on term graphs, or systems of recursion equations, and also suggests the introduction of hidden or nameless nodes in a term graph.
Hy+
95 Citations1993Mariano P. Consens, Alberto O. Mendelzon
This paper provides abrief overview of Hy+, ahygraphbased query and visualization system, which provides a user interface with extensive support for visualizing structural data as hygraphs (of which labelled graphs are a special case).
ACM Transactions on Software Engineering and MethodologyBuilding integrated software development environments. Part I
90 Citations1992Gregor Engels, Claus Lewerentz +3 more
Why and how a graph grammar-based strongly typed language is perfectly suitable to formally specify highly integrated software tools and that the implementation of these tools is systematically being derived from the formal specifications is shown.
Fundamenta InformaticaeTermination of Graph Rewriting is Undecidable
78 Citations1998Detlef Plump
It is shown that it is undecidable in general whether a graph rewriting system (in the “double pushout approach”) is terminating and there is no straightforward reduction of the halting problem for Turing machines or of the termination problem for string rewriting systems to the present problem.
Information SystemsGras, a graph-oriented (software) engineering database system
74 Citations1995N. Kiesel, Andy Schuerr +1 more
The underlying data model and the functionality of GRAS, a database system which has been designed according to the requirements of software engineering, CAD, or office automation, are described.
ACM Transactions on Programming Languages and SystemsOn the adequacy of graph rewriting for simulating term rewriting
67 Citations1994Richard Kennaway, Jan Willem Klop +2 more
This work formalizes the close correspondence between finitary cyclic graph rewriting and a restricted form of infinitary term rewriting, called rational term rewriting.
Graph Grammars with Application Conditions
62 Citations1986Hartmut Ehrig, Annegret Habel
This extended approach to the algebraic theory of graph grammars is applied to a small library system in order to show the flexibility of this concept for the design of systems in computer science and related areas.
Lecture notes in computer scienceSet theoretic approaches to graph grammars
55 Citations1987Manfred Nagl
This paper sketches the approaches of a certain branch of graph grammars mainly studied at Erlangen, Osnabruck, Koblenz and Aachen, West Germany, named set theoretic, or expression, or algorithmic approach of graph Grammars, because its mathematical base is elementary set theory.
RAIRO - Theoretical Informatics and ApplicationsImplementing term rewriting by jungle evaluation
48 Citations1991Berthold Hoffmann, Detlef Plump
On montre that les systemes de reecriture a terminaison finie definissent des systemes d'evaluation de jungles a termine finie capables de normaliser chaque terme.
International Journal of Software Engineering and Knowledge EngineeringNested Graph Transformation Units
48 Citations1997Hans‐Jörg Kreowski, Sabine Kuske +1 more
A new concept for the structured development of rule-based graph transformation systems that allows to build up large systems from small pieces in a modular way is introduced.
Theoretical Computer ScienceCharacteristics of graph languages generated by edge replacement
44 Citations1987Annegret Habel, Hans‐Jörg Kreowski
It is shown that the languages are fixed points of their productions and that they can be generated by language operations from finite graph languages.
Theoretical Computer ScienceComputation on graph-like expressions
43 Citations1980John Staples
A theory of graph-like expressions is developed as far as the basic theoretical result which underlies the remainder of the study of efficient evaluations of expressions, which shows that for a wide class of expressions there are theoretical benefits in allowing graph- like expressions in evaluation algorithms.
Lecture notes in computer scienceProgrammed graph grammars
40 Citations2005Horst Bunke
Let [enum], [exp- i] and [pr-i] denote the class of recursively enumerable, typ- i expression and typ-i programmed graph languages respectively.
Lecture notes in computer scienceOn the interleaving semantics of transformation units — A step into GRACE
37 Citations1996Hans‐Jörg Kreowski, Sabine Kuske
The notion of a transformation unit together with its interleaving semantics is introduced and to study it as a means of constructing large graph transformation systems from small ones in a structured and systematic way.
Journal of Visual Languages & ComputingA Hybrid Query Language for an Extended Entity-Relationship Model
35 Citations1996Marc Andries, Gregor Engels
This work presents the hybrid query language HQL/EER for an Extended Entity-Relationship model and demonstrates the look-and-feel of this query language, and shows how syntax and semantics of this language are formally defined using programmed graph rewriting systems.
Lecture notes in computer scienceNondeterministic control structures for graph rewriting systems
34 Citations1992Albert Zündorf, Andy Schürr
The work reported here is part of the IPSEN3 project whose very goal is the development of an Integrated Project Support ENvironment, where directed, attributed, node- and edge- labeled graphs (diane graphs) are used to model the internal structure of software documents.
Lecture notes in computer scienceAgg — An implementation of algebraic graph rewriting
33 Citations1993M. J. S. Lowe, Martin K. Beyer
The Agg-system (Algebraic Graph Grammar System) is a prototype implementation of the algebraic approach to graph transformation that consists of a flexible graphical editor and a derivation component.
International Journal of Foundations of Computer ScienceREDEX CAPTURING IN TERM GRAPH REWRITING
32 Citations1990William M. Farmer, Ronald Watro
It is shown, using results about infinite rewritings of trees, that term graph rewriting with arbitrary structure sharing (including redex capturing) is sound for left-linear term rewrite systems.
Lecture notes in computer scienceAn efficient implementation of graph grammars based on the RETE matching algorithm
32 Citations2005Horst Bunke, T. Glauser +1 more
A new algorithm is proposed that is a generalization of a similar algorithm originally developed for forward chaining production systems that can be used for efficient determination of the set of productions of a graph grammar that are applicable in one rewriting step.
Theoretical Computer ScienceHyperedge replacement jungle rewriting for term-rewriting systems and logic programming
31 Citations1993Andrea Corradini, Francesca Rossi
Information SystemsSQL/EER—syntax and semantics of an Entity-Relationship-based query language
30 Citations1992Uwe Hohenstein, Gregor Engels
High-level query language SQL/EER directly supports all the concepts of the EER model and takes into account well-known features that are integral part of contemporary query languages, e.g. arithmetic and aggregate functions.
Lecture notes in computer scienceOn termination of graph rewriting
30 Citations1995Detlef Plump
A necessary and sufficient condition for termination of graph rewriting systems is established, being certain minimal derivations in which each step depends on previous steps, which characterizes termination of arbitrary term rewriting systems under graph rewriting.
Lecture notes in computer scienceJungle evaluation for efficient term rewriting
29 Citations1988Berthold Hoffmann, Detlef Plump
Jungles are acyclic hypergraphs that represent sets of terms over a signature so that equal subterms can be shared.
Lecture notes in computer scienceAn introduction to the NLC way of rewriting graphs
28 Citations1987Grzegorz Rozenberg
This paper presents an introduction to the rewriting mechanism of Node-Label Controlled (NLC) graph grammars, and presents a more general framework from which NLC graph Grammars are obtained through a number of restrictions.
Lecture notes in computer scienceIs parallelism already concurrency? Part 1: Derivations in graph grammars
27 Citations1987Hans‐Jörg Kreowski
It turns out that each equivalence class in the theory of graph grammars is uniquely represented by a canonical derivation, which is minimal with respect to a delay index.
Lecture notes in computer scienceAmalgamated graph transformations and their use for specifying AGG — an algebraic graph grammar system
26 Citations1994Gabriele Taentzer, Martin K. Beyer
The Agg-system is a prototype implementation of the algebraic approach to graph transformation that consists of a flexible graph editor and a transformation component that performs direct transformation steps for user-selected production rules and occurrences.
Information SciencesOn structured graph grammars. II
24 Citations1990Hans‐Jörg Kreowski, Grzegorz Rozenberg
This paper takes a closer look at various basic features of this framework of sequential graph rewriting and demonstrates how various existing approaches fit into it.
Electronic Notes in Theoretical Computer ScienceDIEGO, Another Step Towards a Module Concept for Graph Transformation Systems
24 Citations1995Gabriele Taentzer, Andy Schürr
DIEGO module systems offer means for Distributed programming with Encapsulated Graph Objects, and their operational semantics definition follows the lines of distributed graph transformation, thereby permitting the specification of distributed systems with concurrently interacting objects.
Theoretical Computer ScienceComputing with graph rewriting systems with priorities
23 Citations1993Igor Litovsky, Yves Métivier
The notion of safe PGRS with respect to a given property is defined and the classes of sets of graphs (1-graphs) so defined are compared with the classes definable by logic formulas.
GOOD
23 Citations1993Marc Gemis, Jan Paredaens +2 more
This video session demonstrates a graph oriented database management system called GOOD and develops a language that simplifies the information retrieval and modi cation of such a graph.
Lecture notes in computer scienceGraph unification and matching
23 Citations1996Detlef Plump, Annegret Habel
The matching concept suggests a new graph rewriting approach which is very simple to describe and which generalizes the well-known double-pushout approach.
Lecture notes in computer sciencePragmatic and semantic aspects of a module concept for graph transformation systems
21 Citations1996Hartmut Ehrig, Gregor Engels
The paper presents a conceptual framework for a module concept for graph transformation systems from a software engineering as well as from a theoretical point of view to reuse concepts, which are known within or without the graph grammar field, to structure large specifications.
Lecture notes in computer scienceCritical pairs in term graph rewriting
20 Citations1994Detlef Plump
The present paper introduces critical pairs in term graph rewriting and establishes a Critical Pair Lemma as an analogue to the well-known result in term rewriting, which leads to a decision procedure for confluence in the presence of termination.
Information SciencesOn structured graph grammars. I
17 Citations1990Hans‐Jörg Kreowski, Grzegorz Rozenberg
This paper presents a antion of a (seq~e~tial~ graph grammar which formalizes the graph rewriting process based on the above sequence of steps, and provides a basis for singling out the essential differences and similarities between various notions of a graph grammar studied in the literature.
ComputingOn the generative power of sequential and parallel programmed graph grammars
17 Citations1982Horst Bunke
Programmed graph grammars are formally introduced and their generative power is investigated and several classes of graph languages are compared mutually as well as with the hierarchy introduced by Nagl.
Theoretical Computer ScienceGraph grammars and operational semantics
17 Citations1982Peter Padawitz
It is shown that a LISP interpreter represented by a graph grammar is correct with respect to the functional semantics of graphlike LISp expressions.
Lecture notes in computer scienceGraph grammars and logic programming
16 Citations2005Andrea Corradini, Ugo Montanari +3 more
The main result of the paper states the soundness and completeness of the representation of clauses by productions, and this correspondence is extended to entire computations, showing how a context-free grammar (over a suitable category of graphs) can be associated with a logic program.
Lecture notes in computer scienceCollapsed tree rewriting: Completeness, confluence, and modularity
16 Citations1993Detlef Plump
It is shown that collapsed tree rewriting is complete with respect to equational validity in the same sense as term rewriting is, and Termination and convergence of collapsed tree rewrite turn out to be modular properties, in contrast to the situation for term rewriting.
Lecture notes in computer scienceImplementing term rewriting by graph reduction: Termination of combined systems
16 Citations1991Detlef Plump
It is shown that the disjoint union of terminating term rewriting systems does not yield a terminating system in general, and it is proved that the graph reduction system for the union ℝ0∪ℝ1 is terminating provided that the left-hand sides of �” i have no common function symbols with the right-hand side of ™1−i.
Lecture notes in computer scienceGraphEd: An interactive tool for developing graph grammars
15 Citations2005Michael Himsolt
GraphEd is a powerful interactive editor for drawing and manipulating graphs and graph grammars that helps designing graphs, networks, data structures, entity relationship diagrams, petri nets, electrical circuits, VLSI circuits, flowcharts or even arbitrary diagrams.
Theoretical Computer ScienceModularity in noncopying term rewriting
15 Citations1995Masahito Kurihara, Azuma Ohuchi
This paper introduces a class of “noncopying” term rewriting systems as a new, term-based formalism for a kind of graph rewriting systems, and proves that this class enjoys the modularity of termination and of completeness.
RWTH Publications (RWTH Aachen)Rapid Programming with Graph Rewrite Rules
15 Citations1994Andy Schürr
Mathematical Structures in Computer ScienceTerm graph narrowing
14 Citations1996Annegret Habel, Detlef Plump
This work introduces term graph narrowing as an approach for solving equations by transformations on term graphs and concludes that this mechanism is complete for all term rewriting systems over which term graph rewriting is normalizing and confluent.
Lecture notes in computer scienceSimplification orders for term graph rewriting
13 Citations1997Detlef Plump
In this paper, simplification orders on term graphs are introduced as a means for proving termination of term graph rewriting, based on an extension of the homeomorphic embedding relation from trees to term graphs.
Lecture notes in computer sciencePLAND2D — Towards a Two-Dimensional Programming Language
13 Citations1975Ernst Denert, Reinhold Franck +1 more
Electronic Notes in Theoretical Computer ScienceA Compositional Approach to Structuring and Refinement of Typed Graph Grammars
12 Citations1995Andrea Corradini, Reiko Heckel
Colimits (pushouts) are used to model composition and (reverse) graph grammar morphisms to describe refinements of typed graph grammars to preserve the structure of a composed grammar and common subgrammars is shown to be compatible with the semantics.
Lecture notes in computer scienceGraph-reducible term rewriting systems
9 Citations2005Detlef Plump
A broad class of term rewriting systems which includes all terminating and all orthogonal systems can be shown to be graph-reducible.
Lecture notes in computer scienceFive facets of hyperedge replacement beyond context-freeness
7 Citations1993Hans -Jörg Kreowski
Hyperedge replacement is studied for more than twenty years as a rulebased device for the generation of sets of graphs, hypergraphs and other graphlike structures providing mainly a graph-grammatical counterpart to context-free Chomsky grammars.
Lecture notes in computer scienceUnlimp uniqueness as a leitmotiv for implementation
7 Citations2006Stefan Kahrs
When evaluation in functional programming languages is explained using λ-calculus and/or term rewriting systems, expressions and function definitions are often defined as terms, that is as trees, where the collection of all terms is defined as a forest.
Lecture notes in computer scienceTerm rewriting with sharing and memoïzation
7 Citations2005Berthold Hoffmann
Jungle evaluation is an approach to define term rewriting with sharing with sharing based on graph grammars that preserves important properties of term rewriting like termination, and confluence for terminating systems (under mild restrictions).
Lecture notes in computer scienceComparing λ-calculus translations in sharing graphs
5 Citations1995Andrea Asperti, Cosimo Laneve
All the sharing graph encodings turn out to be equivalent modulo the way of counting bus levels, passing through the so called bus-notation.
Lecture notes in computer scienceJungle rewriting: An abstract description of a lazy narrowing machine
4 Citations1994Andrea Corradini, Dietmar Wolz
Jungle Rewriting, a graph rewriting formalism, is used as a formal specification tool for the LANAM, an abstract machine implementing lazy narrowing, and is proved to be essentially equivalent to the given program.
Syntax and Semantics of Hybrid Database Languages
3 Citations1994Marc Andries, Gregor Engels
Acta InformaticaA kernel language for programmed rewriting of (hyper)graphs
3 Citations1996Andrea Maggiolo–Schettini, J x F zef Winkowski
A formalism for rewriting (hyper)graphs in a controlled manner is presented, essentially a simple programming language with productions, that is rewriting rules, playing the role of basic instructions.
Acta InformaticaA kernel language for programmed rewriting of (hyper)graphs
3 Citations1996Andrea Maggiolo–Schettini, Józef Winkowski
A formalism for rewriting (hyper)graphs in a controlled manner is presented, which is essentially a simple programming language with productions, that is rewriting rules, playing the role of basic instructions.
Information and ComputationBisimilarity in Term Graph Rewriting
1 Citations2000Zena M. Ariola, Jan Willem Klop +1 more
A survey of confluence properties of (acyclic) term graph rewriting and addressing rewriting modulo bisimilarity, that is, rewriting of bisimilarities classes of term graphs.
…