Title: Hierarchical Higher-Order Port Graph Rewriting as a Modelling Language

Abstract: In this talk I will present hierarchical higher-order port graphs (HHOP) and a notion of strategic HHOP-rewriting, as a foundation for modelling tools.

Graph rewriting is a universal modelling paradigm with a formal semantics that enables formal reasoning and analysis of the modelled systems. It can be used for rapid prototyping, to run simulations and also to check system properties. Here we focus on port graphs, which have been used in various domains (e.g., biochemistry, social networks, finance). Intuitively, port graphs can be seen as graphs where nodes have ports, and edges connect nodes via ports. 

Port graph rewriting is a versatile modelling tool, however, it lacks support for abstraction and modularity, two features needed to develop models incrementally. 

HHOPs extend port graphs to capture both hierarchy (by permitting the nesting of graphs) and  abstraction (by the use of graph variables that represent unknown graphs). 

Hierarchies and abstraction can be encoded into port graphs (this is not surprising since port graph rewriting is Turing complete), but we seek to incorporate these features directly into the modelling language to avoid encodings, which hinder the analysis of the modelled system. To deal with hierarchies and graph variables, we extend the standard notion of port graph morphism that is used to define matching, the basis of rewriting. HHOP-rewriting has a categorical semantics following the Single Pushout approach, which we obtain by generalising Lowe's notion of graph structure.

Since by definition rewriting rules can be applied anywhere in a graph, strategies are needed to control the generation of rewriting steps. A strategy language is already available for port graph rewriting systems, which permits to specify rewriting positions, rule priorities, etc. Here we will present an extension of the strategy language with constructs to navigate along the hierarchy of graphs.

To illustrate use of strategic HHOP rewriting as a modelling tool we will provide a specification of the lambda-calculus, the computation model underlying the functional programming paradigm.