Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Strategy Language for Graph Rewriting

  • Conference paper
Logic-Based Program Synthesis and Transformation (LOPSTR 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7225))

Abstract

We give a formal semantics for a graph-based programming language, where a program consists of a collection of graph rewriting rules, a user-defined strategy to control the application of rules, and an initial graph to be rewritten. The traditional operators found in strategy languages for term rewriting have been adapted to deal with the more general setting of graph rewriting, and some new constructs have been included in the language to deal with graph traversal and management of rewriting positions in the graph. This language is part of the graph transformation and visualisation environment PORGY.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 72.00
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Andrei, O.: A Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems. PhD thesis, Institut National Polytechnique de Lorraine (2008)

    Google Scholar 

  2. Andrei, O., Fernández, M., Kirchner, H., Melançon, G., Namet, O., Pinaud, B.: PORGY: Strategy driven interactive transformation of graphs. In: Proceedings of TERMGRAPH 2011, Saarbrucken. EPTCS (April 2011)

    Google Scholar 

  3. Andrei, O., Kirchner, H.: A Rewriting Calculus for Multigraphs with Ports. In: Proceedings of RULE 2007. Electronic Notes in Theoretical Computer Science, vol. 219, pp. 67–82 (2008)

    Google Scholar 

  4. Andrei, O., Kirchner, H.: A Higher-Order Graph Calculus for Autonomic Computing. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Golumbic Festschrift. LNCS, vol. 5420, pp. 15–26. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  5. Auber, D.: Tulip – A huge graph visualization framework. In: Mutzel, P., Jünger, M. (eds.) Graph Drawing Software. Mathematics and Visualization, pp. 105–126. Springer (2003)

    Google Scholar 

  6. Balasubramanian, D., Narayanan, A., van Buskirk, C.P., Karsai, G.: The Graph Rewriting and Transformation Language: GReAT. ECEASST 1 (2006)

    Google Scholar 

  7. Balland, E., Brauner, P., Kopetz, R., Moreau, P.-E., Reilles, A.: Tom: Piggybacking Rewriting on Java. In: Baader, F. (ed.) RTA 2007. LNCS, vol. 4533, pp. 36–47. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Barendregt, H.: The Lambda Calculus, Its Syntax and Semantics. North-Holland (1981)

    Google Scholar 

  9. Barendregt, H., van Eekelen, M., Glauert, J., Kennaway, J.R., Plasmeijer, M., Sleep, M.: Term Graph Rewriting. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds.) PARLE 1987. LNCS, vol. 259, pp. 141–158. Springer, Heidelberg (1987)

    Chapter  Google Scholar 

  10. Barthelmann, K.: How to construct a hyperedge replacement system for a context-free set of hypergraphs. Technical report, Universität Mainz, Institut für Informatik (1996)

    Google Scholar 

  11. Borovanský, P., Kirchner, C., Kirchner, H., Moreau, P.-E., Ringeissen, C.: An overview of ELAN. ENTCS 15 (1998)

    Google Scholar 

  12. Bourdier, T., Cirstea, H., Dougherty, D.J., Kirchner, H.: Extensional and intensional strategies. In: Proceedings Ninth International Workshop on Reduction Strategies in Rewriting and Programming. EPTCS, vol. 15, pp. 1–19 (2009)

    Google Scholar 

  13. Bravenboer, M., Kalleberg, K.T., Vermaas, R., Visser, E.: Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming (2008); Special issue on Experimental Systems and Tools

    Google Scholar 

  14. Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation - part i: Basic concepts and double pushout approach. In: Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pp. 163–246. World Scientific (1997)

    Google Scholar 

  15. Courcelle, B.: Graph Rewriting: An Algebraic and Logic Approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 193–242. Elsevier, MIT Press (1990)

    Google Scholar 

  16. Dauchet, M.: Simulation of Turing Machines by a Left-Linear Rewrite Rule. In: Dershowitz, N. (ed.) RTA 1989. LNCS, vol. 355, pp. 109–120. Springer, Heidelberg (1989)

    Chapter  Google Scholar 

  17. Dijkstra, E.W.: Selected writings on computing - a personal perspective. Texts and monographs in computer science. Springer (1982)

    Google Scholar 

  18. Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformations, vol. 1–3. World Scientific (1997)

    Google Scholar 

  19. Ermel, C., Rudolf, M., Taentzer, G.: The AGG approach: Language and environment. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, pp. 551–603. World Scientific (1997)

    Google Scholar 

  20. Fernández, M., Namet, O.: Strategic programming on graph rewriting systems. In: Proceedings International Workshop on Strategies in Rewriting, Proving, and Programming, IWS 2010. EPTCS, vol. 44, pp. 1–20 (2010)

    Google Scholar 

  21. Geiß, R., Batz, G.V., Grund, D., Hack, S., Szalkowski, A.: GrGen: A Fast SPO-Based Graph Rewriting Tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 383–397. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  22. Habel, A., Müller, J., Plump, D.: Double-pushout graph transformation revisited. Mathematical Structures in Computer Science 11(5), 637–688 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  23. Habel, A., Plump, D.: Computational Completeness of Programming Languages Based on Graph Transformation. In: Honsell, F., Miculan, M. (eds.) FOSSACS 2001. LNCS, vol. 2030, pp. 230–245. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  24. Hanus, M.: Curry: A multi-paradigm declarative language (system description). In: Twelfth Workshop Logic Programming, WLP 1997, Munich (1997)

    Google Scholar 

  25. Jones, S.L.P.: Haskell 98 language and libraries: the revised report. Cambridge University Press (2003)

    Google Scholar 

  26. Kirchner, C., Kirchner, F., Kirchner, H.: Strategic computations and deductions. In: Reasoning in Simple Type Theory. Studies in Logic and the Foundations of Mathematics, vol. 17, pp. 339–364. College Publications (2008)

    Google Scholar 

  27. Lafont, Y.: Interaction nets. In: Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL 1990), pp. 95–108. ACM Press (1990)

    Google Scholar 

  28. Lucas, S.: Strategies in programming languages today. Electr. Notes Theor. Comput. Sci. 124(2), 113–118 (2005)

    Article  Google Scholar 

  29. Martí-Oliet, N., Meseguer, J., Verdejo, A.: Towards a strategy language for Maude. Electr. Notes Theor. Comput. Sci. 117, 417–441 (2005)

    Article  Google Scholar 

  30. Martí-Oliet, N., Meseguer, J., Verdejo, A.: A rewriting semantics for Maude strategies. Electr. Notes Theor. Comput. Sci. 238(3), 227–247 (2008)

    Article  Google Scholar 

  31. Namet, O.: Strategic Modelling with Graph Rewriting Tools. PhD thesis, King’s College London (2011)

    Google Scholar 

  32. Nickel, U., Niere, J., Zündorf, A.: The FUJABA environment. In: ICSE, pp. 742–745 (2000)

    Google Scholar 

  33. Plasmeijer, M.J., van Eekelen, M.C.J.D.: Functional Programming and Parallel Graph Rewriting. Addison-Wesley (1993)

    Google Scholar 

  34. Plotkin, G.D.: A structural approach to operational semantics. J. Log. Algebr. Program. 60-61, 17–139 (2004)

    Google Scholar 

  35. Plump, D.: Term graph rewriting. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, pp. 3–61. World Scientific (1998)

    Google Scholar 

  36. Plump, D.: The Graph Programming Language GP. In: Bozapalidis, S., Rahonis, G. (eds.) CAI 2009. LNCS, vol. 5725, pp. 99–122. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  37. Rensink, A.: The GROOVE Simulator: A Tool for State Space Generation. In: Pfaltz, J.L., Nagl, M., Böhlen, B. (eds.) AGTIVE 2003. LNCS, vol. 3062, pp. 479–485. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  38. Rosu, G., Serbanuta, T.-F.: An overview of the K semantic framework. J. Log. Algebr. Program. 79(6), 397–434 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  39. Schürr, A., Winter, A.J., Zündorf, A.: The PROGRES Approach: Language and Environment. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, pp. 479–546. World Scientific (1997)

    Google Scholar 

  40. Terese. Term Rewriting Systems. Cambridge University Press (2003); Bezem, M., Klop, J.W., de Vrijer, R. (eds)

    Google Scholar 

  41. Thiemann, R., Sternagel, C., Giesl, J., Schneider-Kamp, P.: Loops under strategies... continued. In: Proceedings International Workshop on Strategies in Rewriting, Proving, and Programming. EPTCS, vol. 44, pp. 51–65 (2010)

    Google Scholar 

  42. Visser, E.: Stratego: A Language for Program Transformation Based on Rewriting Strategies. System Description of Stratego. In: Middeldorp, A. (ed.) RTA 2001. LNCS, vol. 2051, pp. 357–361. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  43. Visser, E.: A survey of strategies in rule-based program transformation systems. J. Symb. Comput. 40(1), 831–873 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, King’s College London, London, WC2R 2LS, UK

    Maribel Fernández & Olivier Namet

  2. Inria, Domaine de Voluceau - Rocquencourt, B.P. 105, 78153, Le Chesnay, France

    Hélène Kirchner

Authors
  1. Maribel Fernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hélène Kirchner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olivier Namet
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. MiST, DSIC, Universitat Politècnica de València, Camino de Vera, S/N, 46022, Valencia, Spain

    Germán Vidal

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fernández, M., Kirchner, H., Namet, O. (2012). A Strategy Language for Graph Rewriting. In: Vidal, G. (eds) Logic-Based Program Synthesis and Transformation. LOPSTR 2011. Lecture Notes in Computer Science, vol 7225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32211-2_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-32211-2_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-32210-5

  • Online ISBN: 978-3-642-32211-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation