Search

We present a method for generating random hypergraphs in context-free hypergraph languages. It is obtained by adapting Mairson's generation algorithm for context-free string grammars to the setting of hyperedge replacement grammars. Our main results are that for non-ambiguous hyperedge replacement grammars, the method generates hypergraphs uniformly at random and in quadratic time. We illustrate our approach by a running example of a hyperedge replacement grammar generating term graphs., Comment: In Proceedings DCM 2023, arXiv:2409.19298

As AI solutions enter safety-critical products, the explainability and interpretability of solutions generated by AI products become increasingly important. In the long term, such explanations are the key to gaining users' acceptance of AI-based systems' decisions. We report on applying a model-driven-based optimisation to search for an interpretable and explainable policy that solves the game 2048. This paper describes a solution to the GECCO'24 Interpretable Control Competition using the open-source software EvoAl. We aimed to develop an approach for creating interpretable policies that are easy to adapt to new ideas., Comment: 2 pages, GECCO'24 competition entry

In this paper, we utilize Isabelle/HOL to develop a formal framework for the basic theory of double-pushout graph transformation. Our work includes defining essential concepts like graphs, morphisms, pushouts, and pullbacks, and demonstrating their properties. We establish the uniqueness of derivations, drawing upon Rosens 1975 research, and verify the Church-Rosser theorem using Ehrigs and Kreowskis 1976 proof, thereby demonstrating the effectiveness of our formalisation approach. The paper details our methodology in employing Isabelle/HOL, including key design decisions that shaped the current iteration. We explore the technical complexities involved in applying higher-order logic, aiming to give readers an insightful perspective into the engaging aspects of working with an Interactive Theorem Prover. This work emphasizes the increasing importance of formal verification tools in clarifying complex mathematical concepts.

We present a computation model based on a subclass of GP 2 graph programs which can simulate any off-line Turing machine of space complexity O(s(n) log s(n)) in space O(s(n)). The simulation only requires a quadratic time overhead. Our model shares this property with Sch\"onhage's storage modification machines and Kolmogorov-Uspenskii machines. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs., Comment: In Proceedings GCM 2022, arXiv:2212.10975

We formalise the basics of the double-pushout approach to graph transformation in the proof assistant Isabelle/HOL and provide associated machine-checked proofs. Specifically, we formalise graphs, graph morphisms and rules, and a definition of direct derivations based on deletion and gluing. We then formalise graph pushouts and prove with Isabelle's help that both deletions and gluings are pushouts. We also prove that pushouts are unique up to isomorphism. The formalisation comprises around 2000 lines of source text. Our motivation is to pave the way for rigorous, machine-checked proofs in the theory of the double-pushout approach, and to lay the foundations for verifying graph transformation systems and rule-based graph programs by interactive theorem proving., Comment: In Proceedings GCM 2022, arXiv:2212.10975

The operational semantics of a programming language is said to be small-step if each transition step is an atomic computation step in the language. A semantics with this property faithfully corresponds to the implementation of the language. The previous semantics of the graph programming language GP 2 is not fully small-step because the loop and branching commands are defined in big-step style. In this paper, we present a truly small-step operational semantics for GP 2 which, in particular, accurately models diverging computations. To obtain small-step definitions of all commands, we equip the transition relation with a stack of host graphs and associated operations. We prove that the new semantics is non-blocking in that every computation either diverges or eventually produces a result graph or the failure state. We also show the finite nondeterminism property, viz. that each configuration has only a finite number of direct successors. The previous semantics of GP 2 is neither non-blocking nor does it have the finite nondeterminism property. We also show that, for a program and a graph that terminate, both semantics are equivalent, and that the old semantics can be simulated with the new one., Comment: In Proceedings GCM 2021, arXiv:2112.10217

The transformation of graphs and graph-like structures is ubiquitous in computer science. When a system is described by graph-transformation rules, it is often desirable that the rules are both terminating and confluent so that rule applications in an arbitrary order produce unique resulting graphs. However, there are application scenarios where the rules are not globally confluent but confluent on a subclass of graphs that are of interest. In other words, non-resolvable conflicts can only occur on graphs that are considered as "garbage". In this paper, we introduce the notion of confluence up to garbage and generalise Plump's critical pair lemma for double-pushout graph transformation, providing a sufficient condition for confluence up to garbage by non-garbage critical pair analysis. We apply our results in two case studies about efficient language recognition: we present backtracking-free graph reduction systems which recognise a class of flow diagrams and a class of labelled series-parallel graphs, respectively. Both systems are non-confluent but confluent up to garbage. We also give a critical pair condition for subcommutativity up to garbage which, together with closedness, implies confluence up to garbage even in non-terminating systems., Comment: 33 pages, 2021

Implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. In this paper, we present a number of linear-time implementations of graph algorithms in GP 2, an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. We focus on two classes of rule-based graph programs: graph reduction programs which check some graph property, and programs using a depth-first search to test some property or perform an operation such as producing a 2-colouring or a topological sorting. Programs of the first type run in linear time without any constraints on input graphs while programs of the second type require input graphs of bounded degree to run in linear time. Essential for achieving the linear time complexity are so-called rooted rules in GP 2, which, in many situations, can be matched in constant time. For each of our programs, we prove both correctness and complexity, and also give empirical evidence for their run time., Comment: 47 pages, 2020

We consider Hoare-style verification for the graph programming language GP 2. In previous work, graph properties were specified by so-called E-conditions which extend nested graph conditions. However, this type of assertions is not easy to comprehend by programmers that are used to formal specifications in standard first-order logic. In this paper, we present an approach to verify GP 2 programs with a standard first-order logic. We show how to construct a strongest liberal postcondition with respect to a rule schema and a precondition. We then extend this construction to obtain strongest liberal postconditions for arbitrary loop-free programs. Compared with previous work, this allows to reason about a vastly generalised class of graph programs. In particular, many programs with nested loops can be verified with the new calculus., Comment: In Proceedings GCM 2020, arXiv:2012.01181. arXiv admin note: substantial text overlap with arXiv:2010.14549

When using graph transformation rules to implement graph algorithms, a challenge is to match the efficiency of programs in conventional languages. To help overcome that challenge, the graph programming language GP 2 features rooted rules which, under mild conditions, can match in constant time on bounded degree graphs. In this paper, we present an efficient GP 2 program for computing minimum spanning trees. We provide empirical performance results as evidence for the program's subquadratic complexity on bounded degree graphs. This is achieved using depth-first search as well as rooted graph transformation. The program is based on Boruvka's algorithm for minimum spanning trees. Our performance results show that the program's time complexity is consistent with that of classical implementations of Boruvka's algorithm, namely O(m log n), where m is the number of edges and n the number of nodes., Comment: In Proceedings GCM 2020, arXiv:2012.01181

We consider Hoare-style verification for the graph programming language GP 2. In previous work, graph properties were specified by so-called E-conditions which extend nested graph conditions. However, this type of assertions is not easy to comprehend by programmers that are used to formal specifications in standard first-order logic. In this paper, we present an approach to verify GP 2 programs with a standard first-order logic. We show how to construct a strongest liberal postcondition with respect to a rule schema and a precondition. We then extend this construction to obtain strongest liberal postconditions for arbitrary loop-free programs. Compared with previous work, this allows to reason about a vastly generalised class of graph programs. In particular, many programs with nested loops can be verified with the new calculus., Comment: Extended version of a paper to appear at GCM 2020 post-proceeding

GP 2 is a rule-based programming language based on graph transformation rules which aims to facilitate program analysis and verification. Writing efficient programs in such a language is challenging because graph matching is expensive. GP 2 addresses this problem by providing rooted rules which, under mild conditions, can be matched in constant time. Recently, we implemented a number of changes to Bak's GP 2-to-C compiler in order to speed up graph programs. One key improvement is a new data structure for dynamic arrays called BigArray. This is an array of pointers to arrays of entries, successively doubling in size. To demonstrate the speed-up achievable with the new implementation, we present a reduction program for recognising binary DAGs which previously ran in quadratic time but now runs in linear time when compiled with the new compiler., Comment: 11 pages, 2020. arXiv admin note: substantial text overlap with arXiv:2002.02914

GP 2 is an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. Writing efficient programs in such a language is hard because graph matching is expensive, however GP 2 addresses this problem by providing rooted rules which, under mild conditions, can be matched in constant time using the GP 2 to C compiler. In this report, we document various improvements made to the compiler; most notably the introduction of node lists to improve iteration performance for destructive programs, meaning that binary DAG recognition by reduction need only take linear time where the previous implementation required quadratic time., Comment: Technical Report, Department of Computer Science, University of York, 42 pages, 2019

This volume contains the post-proceedings of the Tenth International Workshop on Graph Computation Models (GCM 2019: http://gcm2019.imag.fr). The workshop was held in Eindhoven, The Netherlands, on July 17th, 2019, as part of STAF 2019 (Software Technologies: Applications and Foundations). Graphs are common mathematical structures that are visual and intuitive. They constitute a natural and seamless way for system modelling in science, engineering and beyond, including computer science, biology, business process modelling, etc. Graph computation models constitute a class of very high-level models where graphs are first-class citizens. The aim of the International GCM Workshop series is to bring together researchers interested in all aspects of computation models based on graphs and graph transformation. It promotes the cross-fertilizing exchange of ideas and experiences among senior and young researchers from the different communities interested in the foundations, applications, and implementations of graph computation models and related areas. These post-proceedings contain four selected papers from GCM2019 proceedings and an invited presentation that gives an account of the very successful panel discussion dedicated to the Analysis of Graph Transformation Systems, which took place during the workshop and was animated by Reiko Heckel, Leen Lambers and Maryam Ghaffari Saadat. All submissions were subject to careful refereeing. The topics of accepted papers include theoretical aspects of graph transformation and parsing techniques as well as an application to model-driven engineering.

Graph transformation is the rule-based modification of graphs, and is a discipline dating back to the 1970s. In general, to match the left-hand graph of a fixed rule within a host graph requires polynomial time, but to improve matching performance, D\"orr proposed to equip rules and host graphs with distinguished root nodes. This model was implemented by Plump and Bak, but unfortunately, such rules are not invertible. We address this problem by defining rootedness using a partial function into a two-point set rather than pointing graphs with root nodes, meaning derivations are natural double pushouts. Moreover, we give a sufficient condition on rules to give constant time rule application on graphs of bounded degree, and that, the graph class of trees can be recognised in linear time, given an input graph of bounded degree. Finally, we define a new notion of confluence up to garbage and non-garbage critical pairs, showing it is sufficient to require strong joinability of only the non-garbage critical pairs to establish confluence up to garbage. Finally, this new result, presented for conventional graph transformation systems, can be lifted to our rooted setting by encoding node labels and rootedness as looped edges., Comment: Project Report, Department of Computer Science, University of York, 83 pages, 2019. arXiv admin note: substantial text overlap with arXiv:1906.05170

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.

The graph programming language GP 2 allows to apply sets of rule schemata (or "attributed" rules) non-deterministically. To analyse conflicts of programs statically, graphs labelled with expressions are overlayed to construct critical pairs of rule applications. Each overlay induces a system of equations whose solutions represent different conflicts. We present a rule-based unification algorithm for GP expressions that is terminating, sound and complete. For every input equation, the algorithm generates a finite set of substitutions. Soundness means that each of these substitutions solves the input equation. Since GP labels are lists constructed by concatenation, unification modulo associativity and unit law is required. This problem, which is also known as word unification, is infinitary in general but becomes finitary due to GP's rule schema syntax and the assumption that rule schemata are left-linear. Our unification algorithm is complete in that every solution of an input equation is an instance of some substitution in the generated set., Comment: This paper is an extended version of the workshop paper "A Unification Algorithm for GP 2", published in Graph Computation Models (GCM 2014), Revised Selected Papers, Electronic Communications of the EASST, volume 71, 2015, doi: 10.14279/tuj.eceasst.71.1002

GP 2 is a non-deterministic programming language for computing by graph transformation. One of the design goals for GP 2 is syntactic and semantic simplicity, to facilitate formal reasoning about programs. In this paper, we demonstrate with four case studies how programmers can prove termination and partial correctness of their solutions. We argue that GP 2's graph transformation rules, together with induction on the length of program executions, provide a convenient framework for program verification., Comment: In Proceedings TERMGRAPH 2016, arXiv:1609.03014