Search

We introduce a form of neutral horizontal gene transfer (HGT) to evolving graphs by graph programming (EGGP). We introduce the$$\mu \times \lambda$$μ×λevolutionary algorithm (EA), where$$\mu$$μparents each produce$$\lambda$$λchildren who compete only with their parents. HGT events then copy the entire active component of one surviving parent into the inactive component of another parent, exchanging genetic information without reproduction. Experimental results from symbolic regression problems show that the introduction of the$$\mu \times \lambda$$μ×λEA and HGT events improve the performance of EGGP. Comparisons with genetic programming and Cartesian genetic programming strongly favour our proposed approach. We also investigate the effect of using HGT events in neuroevolution tasks. We again find that the introduction of HGT improves the performance of EGGP, demonstrating that HGT is an effective cross-domain mechanism for recombining graphs.

We introduce a form of neutral Horizontal Gene Transfer (HGT) to Evolving Graphs by Graph Programming (EGGP). We introduce the µ × λ evolutionary algorithm, where µ parents each produce λ children who compete with only their parents. HGT events then copy the entire active component of one surviving parent into the inactive component of another parent, exchanging genetic information without reproduction. Experimental results from 14 symbolic regression benchmark problems show that the introduction of the µ × λ EA and HGT events improve the performance of EGGP. Comparisons with Genetic Programming and Cartesian Genetic Programming strongly favour our proposed approach.

We present a method for statically verifying confluence (functional behaviour) of terminating sets of rules in the graph programming language GP 2, which is undecidable in general. In contrast to other work about attributed graph transformation, we do not impose syntactic restrictions on the rules except for left-linearity. Our checking method relies on constructing the symbolic critical pairs of a rule set using an E-unification algorithm and subsequently checking whether all pairs are strongly joinable with symbolic derivations. The correctness of this method is a consequence of the main technical result of this paper, viz. that a set of left-linear attributed rules is locally confluent if all symbolic critical pairs are strongly joinable, and our previous results on the completeness and finiteness of the set of symbolic critical pairs. We also show that for checking strong joinability, it is not necessary to compute all graphs derivable from a critical pair. Instead, it suffices to focus on the pair’s persistent reducts. In a case study, we use our method to verify the confluence of a graph program that calculates shortest distances.

We establish a machine-checkable condition which ensures that the union of two terminating hypergraph transformation systems is terminating. The condition is based on so-called sequential critical pairs which represent consecutive rule applications that are not independent. In contrast to a corresponding modularity result for term rewriting, no restrictions on the form of rules are required. Our result applies to both systems with injective rules and systems with rules that merge nodes or edges.

We present an approach to attributed graph transformation which requires neither infinite graphs containing data algebras nor auxiliary edges that link graph items with their attributes. Instead, we use the double-pushout approach with relabelling and extend it with rule schemata which are instantiated to ordinary rules prior to application. This framework provides the formal basis for the graph programming language GP 2. In this paper, we abstract from the data algebra of GP 2, define parallel independence of rule schema applications, and prove the Church-Rosser Theorem for our approach. The proof relies on the Church-Rosser Theorem for partially labelled graphs and adapts the classical proof by Ehrig and Kreowski, bypassing the technicalities of adhesive categories.

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 first-order term unification. This mechanism is complete for all term rewriting systems over which term graph rewriting is normalizing and confluent. This includes, in particular, all convergent term rewriting systems. Completeness means that for every solution of a given equation, term graph narrowing can find an equivalent or more general solution. The general motivation for using term graphs instead of terms is to improve efficiency: sharing common subterms saves space and avoids the repetition of computations.

When graph transformation is used 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 of hierarchically structured hypergraphs. In these graphs, distinguished hyperedges contain graphs that can be hierarchical again. Our framework extends the well-known double-pushout approach from flat to hierarchical graphs. In particular, we show how pushouts and pushout complements of hierarchical graphs and graph morphisms can be constructed recursively. Moreover, we make rules more expressive by introducing variables which allow us to copy and remove hierarchical subgraphs in a single rule application.

In this paper we investigate and compare four variants of the double-pushout approach to graph transformation. As well as the traditional approach with arbitrary matching and injective right-hand morphisms, we consider three variations by employing injective matching and/or arbitrary right-hand morphisms in rules. We show that injective matching provides additional expressiveness in two respects: for generating graph languages by grammars without non-terminals and for computing graph functions by convergent graph transformation systems. Then we clarify for each of the three variations whether the well-known commutativity, parallelism and concurrency theorems are still valid and – where this is not the case – give modified results. In particular, for the most general approach with injective matching and arbitrary right-hand morphisms, we establish sequential and parallel commutativity by appropriately strengthening sequential and parallel independence.

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 Problem. It is also argued that 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.

The categorical framework of $\mathcal M$-adhesive transformation systems does not cover graph transformation with relabelling. Rules that relabel nodes are natural for computing with graphs, however, and are commonly used in graph transformation languages. In this paper, we generalise $\mathcal M$-adhesive transformation systems to $\mathcal M,\mathcal N$-adhesive transformation systems, where $\mathcal N$ is a class of morphisms containing the vertical morphisms in double-pushouts. We show that the category of partially labelled graphs is $\mathcal M,\mathcal N$-adhesive, where $\mathcal M$ and $\mathcal N$ are the classes of injective and injective, undefinedness-preserving graph morphisms, respectively. We obtain the Local Church-Rosser Theorem and the Parallelism Theorem for graph transformation with relabelling and application conditions as instances of results which we prove at the abstract level of $\mathcal M,\mathcal N$-adhesive systems.

In this paper, we consider a large variety of solutions for the generation of Sierpinski triangles, one of the case studies for the AGTIVE graph transformation tool contest [15]. A Sierpinski triangle shows a well-known fractal structure. This case study is mostly a performance benchmark, involving the construction of all triangles up to a certain number of iterations. Both time and space performance are involved. The transformation rules themselves are quite simple.

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 left-hand sides of rules must be reachable from the root, and nodes must have a bounded outdegree. We establish a constant upper bound for the time needed to construct all graphs resulting from an application of a fixed rule to an input graph. We also give an improved upper bound under the stronger condition that all edges outgoing from a node must have distinct labels. Then this result is applied to identify a class of graph reduction systems that define graph languages with a linear membership test. In a case study we prove that the (non-context-free) language of balanced binary trees with backpointers belongs to this class.

Term rewriting is commonly implemented by graph reduction in order to improve efficiency. In general, however, graph reduction is not complete: a term may be not normalizable through graph derivations although a normal form exists. Term rewriting systems which permit a complete implementation by graph reduction are called graph-reducible. We show that the following property is sufficient for graph-reducibility: every term having a normal form can be normalized by parallel term rewrite steps in which a rule is applied to all occurrences of some subterm. As a consequence, a broad class of term rewriting systems which includes all terminating and all orthogonal systems can be shown to be graph-reducible.

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 pairs are introduced to hypergraph rewriting, a generalisation of graph rewriting, where it turns out that the mere existence of common reducts for all critical pairs of a graph rewriting system does not imply local confluence. A Critical Pair Lemma for hypergraph rewriting is then established which guarantees local confluence if each critical pair of a system has joining derivations that are compatible in that they map certain nodes to the same nodes in the common reduct.

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 numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra’s shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.

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 framework extends the double-pushout approach from flat to hierarchical graphs. In particular, we show how to construct recursively pushouts and pushout complements of hierarchical graphs and graph morphisms. To further enhance the expressiveness of the approach, we also introduce rule schemata with variables which allow to copy and to remove hierarchical subgraphs.

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 consider three variations by employing injective matching and/or arbitrary right-hand morphisms in rules. For each of the three variations, we clarify whether the well-known commutativity theorems are still valid and-where this is not the case-give modified results. In particular, for the most general approach with injective matching and arbitrary right-hand morphisms, we establish sequential and parallel commutativity by appropriately strengthening sequential and parallel independence. We also show that injective matching provides additional expressiveness in two respects, viz. for generating graph languages by grammars without nonterminals and for computing graph functions by convergent graph transformation systems.

Term graph rewriting differs from term rewriting in that common subexpressions can be shared, improving the efficiency of rewriting in space and time. Moreover, computations by term graph rewriting terminate more often than computations by term rewriting. In this paper, simplification orders on term graphs are introduced as a means for proving termination of term graph rewriting. Simplification orders are based on an extension of the homeomorphic embedding relation from trees to term graphs. By generalizing Kruskal's Tree Theorem to term graphs, it is shown that simplification orders are well-founded. Then a recursive path order on term graphs is defined by analogy with the well-known order on terms, and is shown to be a simplification order. Examples of termination proofs with the recursive path order are given for rewrite systems that are non-terminating under term rewriting.

A concept of graph unification and matching is introduced by using hyperedges as graph variables and hyperedge replacement as substitution mechanism. It is shown that a restricted form of graph unification corresponds to solving linear Diophantine equations, and hence is decidable. For graph matching, transformation rules are given which compute all (pure) solutions to a matching problem. The matching concept suggests a new graph rewriting approach which is very simple to describe and which generalizes the well-known double-pushout approach.

A necessary and sufficient condition for termination of graph rewriting systems is established. Termination is equivalent to the finiteness of all forward closures, being certain minimal derivations in which each step depends on previous steps. This characterization differs from corresponding results for term rewriting in that the latter hold only for subclasses of term rewriting systems. When applied to term graph rewriting, the result characterizes termination of arbitrary term rewriting systems under graph rewriting. In particular, it captures non-terminating term rewriting systems that are terminating under graph rewriting.

Term graphs represent functional expressions such that common subexpressions can be shared, making expression evaluation more efficient than with strings or trees. Rewriting of term graphs proceeds by both applications of term rewrite rules and folding steps which enhance the degree of sharing. 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. This leads to a decision procedure for confluence in the presence of termination. As a by-product, the procedure can be used as a confluence test for term rewriting and as such it extends the classical test of Knuth and Bendix because it applies to all terminating and to certain non-terminating term rewriting systems.

Collapsed trees are (hyper)graphs which represent functional expressions such that common subexpressions can be shared. Rewrite steps with collapsed trees include applications of term rewrite rules as well as “folding steps” which identify common subexpressions. Different aspects of this model of computation are considered: (1) It is shown that collapsed tree rewriting is complete with respect to equational validity in the same sense as term rewriting is. (2) Collapsed tree rewriting and term rewriting are compared with respect to confluence. (3) Termination and convergence of collapsed tree rewriting turn out to be modular properties, in contrast to the situation for term rewriting.

It is well known that the disjoint union of terminating term rewriting systems does not yield a terminating system in general. We show that this undesirable phenomenon vanishes if one implements term rewriting by graph reduction: given two terminating term rewrite systems ℝ0 and ℝ1, the graph reduction system implementing ℝ0+ℝ1 is terminating. In fact, we prove the stronger result 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 sides of ℝ1−i (i=0, 1).

We present a survey of confluence properties of (acyclic) term graph rewriting. Results and counterexamples are given for four different kinds of term graph rewriting: besides plain applications of rewrite rules, extensions with the operations of collapsing and copying, and with both operations together are considered. Collapsing and copying together constitute bisimilarity of term graphs. We establish sufficient conditions for, and counterexamples to, confluence and confluence modulo bisimilarity of term graph rewriting over various classes of term rewriting systems.

International audience; Some recent algebraic approaches to graph transformation include a pullback construction involving the match, that allows one to specify the cloning of items of the host graph. We pursue further this trend by proposing the Pullback-Pushout (pb-po) Approach, where we combine smoothly the classical modifications to a host graph specified by a rule (a span of graph morphisms) with the cloning of structures specified by another rule. The approach is shown to be a conservative extension of agree (and thus of the sqpo approach), and we show that it can be extended with standard techniques to attributed graphs. We discuss conditions to ensure a form of locality of transformations, and conditions to ensure that the attribution of transformed graphs is total.