Safe Pointers by Graph Transformation (2008)
This document is a shortened version of the project proposal submitted to EPSRC. Sections with personal or financial details, for example, have been omitted. Summary: Pointers in imperative...
Diagrams for Meaning Preservation ⋆ (2008)
Joe B. Wells, Detlef Plump, Fairouz Kamareddine
Abstract. This paper presents an abstract framework and multiple diagram-based methods for proving meaning preservation, i.e., that all rewrite steps of a rewriting system preserve the meaning given...
GraphTransformationinConstantTime (2008)
Abstract. We present conditions under which graph transformation rules can be applied in time independent of the size of the input graph: graphs must contain a unique root label, nodes in the...
Bisimilarity in term graphs rewriting (2007)
Zena M. Ariola, Jan Willem Klop, Detlef Plump
We present a survey of con uence properties of (acyclic) term graph rewriting. Results and counterexamples are given for dierent kinds of term graph rewriting: besides plain applications of rewrite...
Diagrams for Meaning Preservation ⋆ (2007)
J. B. Wells, Detlef Plump, Fairouz Kamareddine
Abstract. This paper presents an abstract framework and multiple diagram-based methods for proving meaning preservation, i.e., that all rewrite steps of a rewriting system preserve the meaning given...
A Core Language for Graph Transformation (Extended Abstract) (2007)
We show how to program in a core programming language based on graph transformation rules. Our programs compute various functions and relations on graphs: the functions generating the transitive...
The York abstract machine (2006)
We introduce the York Abstract Machine (YAM) for implementing the graph programming language GP and, potentially, other graph transformation languages. The advantages of an abstract machine over a...
Confluence of graph transformation revisited (2005)
Abstract. It is shown that it is undecidable in general whether a terminating graph rewriting system is confluent or not—in contrast to the situation for term and string rewriting systems. Critical...
Extending C for checking shape safety (2005)
The project Safe Pointers by Graph Transformation at the University of York has developed a method for specifying the shape of pointer-data structures by graph reduction, and a static checking...
Towards graph programs for graph algorithms (2004)
Abstract. Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that...
Specifying pointer structures by graph reduction (2003)
Adam Bakewell, Detlef Plump, Colin Runciman
Graph-reduction specifications (GRSs) are a powerful new method for specifying classes of pointer data structures (shapes). They cover important shapes, like various forms of balanced trees, that...
Checking the shape safety of pointer manipulations (2003)
Adam Bakewell, Detlef Plump, Colin Runciman
Abstract. We present a new algorithm for checking the shape-safety of pointer manipulation programs. In our model, an abstract, data-less pointer structure is a graph. Ashape is a language of graphs....
Checking the Shape Safety of Pointer Manipulations (Extended Abstract) (2003)
Adam Bakewell, Detlef Plump, Colin Runciman
Pointers in imperative programming languages are indispensable for the efficient implementation of many algorithms at both application and system level...
Relabelling in graph transformation (2002)
The traditional double-pushout approach to graph transformation does not allow to change node labels in an arbitrary context. We propose a simple solution to this problem, namely to use rules with...
Appligraph: Applications of Graph Transformation - Fifth Annual Progress Report (2002)
Hans-Jörg Kreowski, Detlef Plump (eds.)
This report summarizes the activities in the nal 13 months of the ESPRIT Working Group APPLIGRAPH, covering the period from April 1, 2001, to April 30, 2002. The principal objective of this Working...
Hierarchical Graph Transformation (2002)
Frank Drewes, Berthold Hoffmann, Detlef Plump
When graph transformation is ussed for programming purposes, large graphs should be structured in order to be comprehensible. In this paper, we present an approach for the rule-based transformation...
Hierarchical Graph Transformation (2002)
Frank Drewes, Berthold Hoffmann, Detlef Plump
When graph transformation is used for programming purposes, large graphs should be structured...
Appligraph: Applications of Graph Transformation - Final Report (2002)
Hans-Jörg Kreowski, Detlef Plump (eds.), Detlef Plump
This report summarizes the activities of the ESPRIT Working Group APPLIGRAPH, covering the period from April 1, 1997, to April 30, 2002. The principal objective of this Working Group was to promote...
Relabelling in Graph Transformation (2002)
The traditional double-pushout approach to graph transformation does not allow to change node labels in an arbitrary context. We propose a simple solution to this problem, namely to use rules with...
Computational completeness of programming languages based on graph transformation (2001)
Abstract. We identify a set of programming constructs ensuring that a programming language based on graph transformation is computationally complete. These constructs are (1) nondeterministic...
Solving Equations by Graph Transformation (2001)
We review the concept of term graph narrowing as an approach for solving equations by transformations on term graphs. Term graph narrowing combines term graph rewriting with rst-order term uni...
Hierarchical Graph Transformation (2000)
Frank Drewes, Berthold Hoffmann, Detlef Plump
If systems are specified by graph transformation, large graphs should be structured in order to be comprehensible. In this paper, we present an approach for the rule-based transformation of...
Double-Pushout Graph Transformation Revisited (1999)
Annegret Habel, Jürgen Müller, Detlef Plump
We investigate and compare four variants of the double-pushout approach to graph transformation. Besides the traditional approach with arbitrary matching and injective right-hand morphisms, we...
Hierarchical Graph Transformation (1999)
Frank Drewes, Berthold Hoffmann, Detlef Plump
. We present an approach for the rule-based transformation of hierarchically structured (hyper)graphs. In these graphs, distinguished hyperedges contain graphs that can be hierarchical again. Our...
Complete strategies for term graph narrowing (1999)
Abstract. Narrowing is a method for solving equations in the equational theories of term rewriting systems. Unification and rewriting, the central operations in narrowing, are often implemented on...
Double-pushout approach with injective matching (1999)
Annegret Habel, Jürgen Müller, Detlef Plump
Abstract. We investigate and compare four variants of the doublepushout approach to graph transformation. Besides the traditional approach with arbitrary matching and injective right-hand morphisms,...
Termination Of Graph Rewriting Is Undecidable (1998)
It is shown that it is undecidable in general whether a graph rewriting system (in the "double pushout approach") is terminating. The proof is by a reduction of the Post Correspondence...
Graph Transformation for Specification and Programming (1996)
Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans-Jörg Kreowski, Sabine Kuske, ...
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...
Graph Transformation for Specification and Programming (1996)
Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans-Jörg Kreowski, Sabine Kuske, ...
The aim of this paper is to survey some recent trends in applied graph transformation as a rule based framework for the specification and development of systems, languages, and tools. After recalling...
Graph Transformation for Specification and Programming (1996)
Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans-Jörg Kreowski, Sabine Kuske, ...
The framework of graph transformation combines the potentials and advantages of both, graphs and rules, into a single computational paradigm. In this paper we survey recent developments in applying...
this paper we introduce term graph narrowing as an approach for solving equations by transformations on term graphs. Our main result is that term graph narrowing is complete for all term rewriting...
Unification, Rewriting, and Narrowing on Term Graphs (1995)
The concept of graph substitution recently introduced by the authors is applied to term graphs, yielding a uniform framework for unification, rewriting, and narrowing on term graphs. The notion of...
Implementing Term Rewriting by Jungle Evaluation (1991)
Berthold Hoffmann, Detlef Plump
Jungles are acyclic hypergraphs which represent sets of terms such that common subterms can be shared. Term rewrite rules are translated into jungle evaluation rules which implement parallel term...
Critical Pairs And, Undecidability Of Confluence, Detlef Plump
this paper is the completion of non-confluent systems. One could set up a procedure which adds rules to a system until all critical pairs are strongly joinable, where the new rules should preserve...