Strategic Modelling with Graph Rewriting Tools
type: CreativeWork
description: 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.
abstract: 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.
author: Namet, Olivier
language: eng
date published: 2012-11
date modified: 2026-07-24T02:44:42Z
provider: King's College London
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: King's College London