Search

We introduce the concept of Semantic Neutral Drift (SND) for genetic programming (GP), where we exploit equivalence laws to design semantics preserving mutations guaranteed to preserve individuals’ fitness scores. A number of digital circuit benchmark problems have been implemented with rule-based graph programs and empirically evaluated, demonstrating quantitative improvements in evolutionary performance. Analysis reveals that the benefits of the designed SND reside in more complex processes than simple growth of individuals, and that there are circumstances where it is beneficial to choose otherwise detrimental parameters for a GP system if that facilitates the inclusion of SND.

GP 2 is an experimental programming language for computing by graph transformation. An initial interpreter for GP 2, written in the functional language Haskell, provides a concise and simply structured reference implementation. Despite its simplicity, the performance of the interpreter is sufficient for the comparative investigation of a range of test programs. It also provides a platform for the development of more sophisticated implementations., Comment: In Proceedings GaM 2015, arXiv:1504.02448

We discuss the translation of a simple imperative programming language, high-level random access machines, to the rule-based graph programming language GP 2. By proving the correctness of the translation and using GP 2 programs for encoding and decoding between arbitrary graphs and so-called register graphs, we show that GP 2 is computationally complete in a strong sense: every computable graph function can be directly computed with a GP 2 program which transforms input graphs into output graphs. Moreover, by carefully restricting the form of rules and control constructs in translated programs, we identify simple graph programs as a computationally complete sublanguage of GP 2. Simple programs use unconditional rules and abandon, besides other features, the non-deterministic choice of rules.

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 algorithm for proving the shape safety of graph transformation rules modelling operations on pointer structures. In this paper, we outline how to apply this approach to the C programming language. We extend ANSI C with so-called transformers which model graph transformation rules, and with shape specifications for pointer structures. For the resulting language C-GRS, we present both a translation to C and and an abstraction to graph transformation. Our main result is that the abstraction of transformers to graph transformation rules is correct in that the C code implementing transformers is compatible with the semantics of graph transformation.

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.

So far, a very large amount of work in Natural Language Processing (NLP) rely on trees as the core mathematical structure to represent linguistic informations (e.g. in Chomsky's work). However, some linguistic phenomena do not cope properly with trees. In a former paper, we showed the benefit of encoding linguistic structures by graphs and of using graph rewriting rules to compute on those structures. Justified by some linguistic considerations, graph rewriting is characterized by two features: first, there is no node creation along computations and second, there are non-local edge modifications. Under these hypotheses, we show that uniform termination is undecidable and that non-uniform termination is decidable. We describe two termination techniques based on weights and we give complexity bound on the derivation length for these rewriting system., In Proceedings TERMGRAPH 2013, arXiv:1302.5997

International audience; Boolean interaction systems and hard interaction systems define nets of interacting cells. They are based on the same local interaction principle between two cells as interaction nets but do not allow that the structure of nets may evolve. With boolean nets, it is not possible to create or destroy cells or links between existing cells. They are very similar to hardware circuits but based on an implicit rendez-vous information exchange mechanism. If we want to implement such systems using hardware circuits, it is important to define a set of universal combinators that reduces this task to the implementation of a fixed number of known agents. Here, we show how we can simulate every hard interaction system by a universal boolean interaction system composed of three combinators: a duplicator, a NAND gate and a three-state input/output channel.