Skip to content
julio 9, 2012 / Applied Computing Group

Keynote: “Strategy-Driven Graph Transformations in PORGY”

Strategy-Driven Graph Transformations in PORGY
Maribel Fernández
King’s College London, Strand, London WC2R 2LS, UK
Maribel.Fernandez@kcl.ac.uk

PORGY [2] is a visual and interactive tool designed to facilitate the specification and analysis of complex systems. PORGY uses graphs to represent the system modelled, and graph rewrite rules guided by strategies to describe the dynamics of the system. Graphical languages are widely used for describing complex structures in a visual and intuitive way in a variety of domains, such as software modelling (e.g., UML diagrams), representation of proofs (e.g., proof nets), microprocessor design, XML documents, communication networks, and biological systems, amongst others. Graph transformations (or graph rewriting) are used to define the behaviour of the system modelled. From a theoretical point of view, graph rewriting has solid logic, algebraic and categorical foundations [3, 9], and from a practical point of view, it has many applications in specification, programming, and simulation [4, 5]. When the graphs are large or growing via transformations, or when the number of transformation rules is important, being able to directly interact with the rewriting system becomes crucial to understand the changes in the graph structure. From a naïve point of view, the output of a graph rewriting system is a dynamic graph: a sequence of graphs obtained through a series of modifications (addition/deletion of nodes/edges). However, the study of a rewriting system is actually much more complex. Reasoning about the system’s properties actually involves testing various rewriting scenarios, backtracking to a previously computed graph, possibly updating rules, etc. PORGY, developed in collaboration with INRIA Bordeaux-Sud Ouest (http://gravite.labri.fr/?Projects_%2F_Grants:Porgy:Download), addresses these issues.

Our approach is based on the use of port graphs and port graph rewriting rules [1]. Port-graphs are a specific class of labelled graphs introduced as an abstract representation of proteins, and used to model biochemical interactions and autonomous systems. We illustrate this concept by using port graph transformations to model biochemical systems (biochemical interactions that take part in the regulation of cell proliferation and transformation) and interaction nets. These case studies illustrate the need for highly dynamic graphs, and highlight interesting challenges for graph visualisation. PORGY provides support for the initial task of defining a set of graph rewriting rules, and the graph representing the initial state of the system (the “initial model” in PORGY’s terminology), using a visual editor.

Other crucial issues concern when and where rules are applied. To address this problem, PORGY provides a strategy language to constrain the rewriting derivations, generalising the control structures used in graph-based tools such as PROGRES [10] and GP [8], and rewrite-based programming languages such as Stratego and ELAN. In particular, the strategy language includes control structures that facilitate the implementation of graph traversal algorithms, thanks to the explicit definition of “positions” in a graph, where rules can be applied (we refer the reader to [7] for examples of graph programs in PORGY, and to [6] for the formal semantics of the strategy language). Rewriting derivations can also be visualised, and used in an interactive way, using PORGY’s interface. Designing a graph transformation system is often a complex task, and the analysis and debugging of the system involves exploring how rules operate on graphs, analysing sequences of transformations, backtracking and changing earlier decisions. For this purpose, PORGY’s visual environment offers a view on the rewriting history and ways to select time points in the history where to backtrack.

References

  1. Oana Andrei (2008): A Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems. Ph.D. thesis, Institut National Polytechnique de Lorraine. Available at http://tel.archives-ouvertes.fr/tel-00337558/fr/.
  2. Oana Andrei, Maribel Fernández, Hélène Kirchner, Guy Melançon, Olivier Namet & Bruno Pinaud (2011): PORGY: Strategy-Driven Interactive Transformation of Graphs. Proceedings of the 6th International Workshop on Computing with Terms and Graphs, TERMGRAPH 2011, EPTCS.
  3. Bruno Courcelle (1990): Graph Rewriting: An Algebraic and Logic Approach. In J. van Leeuwen, editor: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Elsevier Science Publishers and MIT Press, pp.193–242.
  4. Hartmut Ehrig, Gregor Engels, Hans-Jörg Kreowski & Grzegorz Rozenberg, editors (1997): Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools. World Scientific.
  5. Hartmut Ehrig, Hans-Jörg Kreowski, Ugo Montanari & Grzegorz Rozenberg, editors (1997): Handbook of Graph Grammars and Computing by Graph Transformations, Volume 3: Concurrency, Parallelism, and Distribution. World Scientific.
  6. Maribel Fernández, Hélène Kirchner & Olivier Namet (2012): A strategy language for graph rewriting. To appear in Proceedings of LOPSTR 2011.
  7. Maribel Fernández & Olivier Namet (2010): Strategic Programming on Graph Rewriting Systems. In: Proc. of the 1st International Workshop on Strategies in Rewriting, Proving, and Programming.
  8. Detlef Plump (2009): The Graph Programming Language GP. In Symeon Bozapalidis & George Rahonis, editors: CAI. Lecture Notes in Computer Science 5725, Springer, pp. 99–122.
  9. Grzegorz Rozenberg, editor (1997): Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific.
  10. Andy Schürr, Andreas J. Winter & Albert Zündorf (1997): The PROGRES Approach: Language and Environment. In: [4]. World Scientific, pp. 479–546.

Para estar diariamente informado síganos en:

Twitter@sistedes2012

y también en:

LinkedInhttp://linkd.in/FVvKIK
Facebookhttps://www.facebook.com/sistedes2012

Coordinación de Publicidad
Jornadas #sistedes2012 {JISBD; PROLE; JCIS}

Anuncios

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s