Strategic Modelling with Graph Rewriting Tools

To model complex systems, graphical formalisms have clear advantages: they are more intuitive and make it easier to visualise a system and convey intuitions or ideas about it. Graph rewriting rules can be used to model their dynamic evolution and from a practical point of view, graph transformations have many applications in specification, programming, and simulation tools. Strategic rewriting has been studied for term rewriting systems, and there are languages that allow the user to specify a strategy controlling the use of rewrite rules and to apply it. For graph rewriting, some graph-transformation languages and tools allow the users to specify the way rules are applied. However, there is no general language that uses positions explicitly to apply rules. The work presented in this thesis describes a new notion of located graphs and a strategy language containing focusing constructs. In a graph, there is no notion of a root so standard term rewriting strategies based on top-down or bottom-up traversals do not make sense in this setting. We solve the problem by introducing the notion of position and banning in our located graphs and strategy language to allow for graph traversals and selective rule application based on location within a graph. Two tools graphPaper and PORGY are also described, which allow users to create graph rewrit¬ing systems and to apply strategies on them to create trace trees forming result sets. Specifically, the full implementation of graphPaper, a tool to create and edit graph rewriting systems, is de¬scribed as well as the implementation of the strategy language into the PORGY system to allow users to view a dynamic trace of the computation of a strategic graph system.

Name dc:type.qualificationname

Doctor of Philosophy

Level dc:type.qualificationlevel

Doctoral Thesis

Grantor dc:publisher.institution

King's College London

Year dc:date.issued

2012

Author dc:creator

• Namet, Olivier

Advisors dc:contributor.advisor

• Fernandez, Maria Isabel
• Mackie, Ian
• Luck, Michael Mordechai

Language dc:language

eng

Identifier

oai:kclpure.kcl.ac.uk:studenttheses/1f93398a-eebc-4654-a362-491f27e7d23b

OAI identifier oai:identifier

oai:kclpure.kcl.ac.uk:studenttheses/1f93398a-eebc-4654-a362-491f27e7d23b