Publications on Graph Programs and GP 2

Graph Programs and the Language GP 2

• B. Courtehoute
  Time and Space Complexity of Rule-Based Graph Programs
  PhD thesis, University of York, 2023.

• G. Campbell, B. Courtehoute and D. Plump
  Fast Rule-Based Graph Programs
  Science of Computer Programming 214, Elsevier, 2022.

• B. Courtehoute and D. Plump
  A Small-Step Operational Semantics for GP 2
  Graph Computation Models (GCM 2021), Revised Selected Papers, Electronic Proceedings in Theoretical Computer Science 350, pages 89-110, 2021.

• G. Campbell, B. Courtehoute and D. Plump
  Linear-Time Graph Algorithms in GP 2
  Proc. 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Volume 139 of Leibniz International Proceedings in Informatics (LIPICS), pages 16:1-16:23, 2019.
  doi: 10.4230/LIPIcs.CALCO.2019.16

• D. Plump
  From Imperative to Rule-based Graph Programs
  Journal of Logical and Algebraic Methods in Programming 88:154-173, Elsevier, 2017.
  doi: 10.1016/j.jlamp.2016.12.001

• C. Bak and D. Plump
  Compiling Graph Programs to C
  Proc. International Conference on Graph Transformation (ICGT 2016). Lecture Notes in Computer Science 9761, pages 102-117. Springer, 2016.
  doi: 10.1007/978-3-319-40530-8_7

• C. Bak
  GP 2: Efficient Implementation of a Graph Programming Language
  PhD thesis, University of York, 2015.

• C. Bak, G. Faulkner, D. Plump and C. Runciman
  A Reference Interpreter for the Graph Programming Language GP 2
  Proc. Graphs as Models (GaM 2015). Electronic Proceedings in Theoretical Computer Science 181, pages 48-64, 2015.
  doi: 10.4204/EPTCS.181.4

• C. Bak and D. Plump
  Rooted Graph Programs
  Proc. International Workshop on Graph Based Tools (GraBaTs 2012). Electronic Communications of the EASST 54, 12 pages, 2012.
  doi: 10.14279/tuj.eceasst.54.780

• D. Plump
  The Design of GP 2
  Proc. International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2011). Electronic Proceedings in Theoretical Computer Science 82, pages 1-16, 2012.
  doi: 10.4204/EPTCS.82.1

• D. Plump and S. Steinert
  The Semantics of Graph Programs
  Proc. Rule-Based Programming (RULE 2009). Electronic Proceedings in Theoretical Computer Science 21, pages 27-38, 2010.
  doi: 10.4204/EPTCS.21.3

• D. Plump
  The Graph Programming Language GP
  Proc. International Conference on Algebraic Informatics (CAI 2009). Lecture Notes in Computer Science 5725, pages 99-122. Springer, 2009.
  doi: 10.1007/978-3-642-03564-7_6

• G. Manning and D. Plump
  The GP Programming System
  Proc. Graph Transformation and Visual Modelling Techniques (GT-VMT 2008). Electronic Communications of the EASST 10, 13 pages, 2008.
  doi: 10.14279/tuj.eceasst.10.150

• G. Manning and D. Plump
  The York Abstract Machine
  Proc. Graph Transformation and Visual Modelling Techniques (GT-VMT 2006). Electronic Notes in Theoretical Computer Science 211, pages 231-240. Elsevier, 2008.
  doi: 10.1016/j.entcs.2008.04.045

• S. Steinert
  The Graph Programming Language GP
  PhD thesis, University of York, 2007

• D. Plump and S. Steinert
  Towards Graph Programs for Graph Algorithms
  Proc. International Conference on Graph Transformation (ICGT 2004) . Lecture Notes in Computer Science 3256, pages 128-143. Springer, 2004.
  doi: 10.1007/978-3-540-30203-2_11

---

Verification of Graph Programs

• C. Poskitt and D. Plump
  Monadic Second-Order Incorrectness Logic for GP 2
  Journal of Logical and Algebraic Methods in Programming 130, Elsevier, 2023.

• G. Wulandari
  Verifying Graph Programs with Monadic Second-Order Logic
  PhD thesis, University of York, 2021.

• G. Wulandari and D. Plump
  Verification of Graph Programs with Monadic Second-Order Logic
  Proc. 14th International Conference on Graph Transformation (ICGT 2021). Lecture Notes in Computer Science 12741, pages 240-261. Springer, 2021.
  doi: 10.1007/978-3-030-78946-6_13

• G. Wulandari and D. Plump
  Verification of Graph Programs with Monadic Second-Order Logic (long version)
  Technical Report. 2021.

• G. Wulandari and D. Plump
  Verification of Graph Programs with First-Order Logic
  Proc. Graph Computation Models (GCM 2020). Electronic Proceeding in Computer Science 330, pages 181-200. 2020.
  doi: 10.4204/EPTCS.330

• G. Wulandari and D. Plump
  Verification of Graph Programs with First-Order Logic (long version)
  Technical Report. 2020.

• G. Wulandari and D. Plump
  Verifying a Copying Garbage Collector in GP 2
  Software Technologies: Applications and Foundations - STAF 2018 Collocated Workshops, Revised Selected Papers. Lecture Notes in Computer Science 11176, pages 479-494. Springer, 2018.
  doi: 10.1007/978-3-030-04771-9_34

• D. Plump
  Reasoning about Graph Programs
  Proc. Computing with Terms and Graphs (TERMGRAPH 2016). Electronic Proceedings in Theoretical Computer Science 225, pages 35-44, 2016.
  doi: 10.4204/EPTCS.225.6

• C. Poskitt and D. Plump
  Verifying Monadic Second-Order Properties of Graph Programs
  Proc. International Conference on Graph Transformation (ICGT 2014). Lecture Notes in Computer Science 8571, pages 33-48. Springer, 2014.
  doi: 10.1007/978-3-319-09108-2_3

• C. Poskitt
  Verification of Graph Programs
  PhD thesis, University of York, 2013

• C. Poskitt and D. Plump
  Verifying Total Correctness of Graph Programs
  Graph Computation Models (GCM 2012), Revised Selected Papers. Electronic Communications of the EASST 61, 20 pages, 2013.
  doi: 10.14279/tuj.eceasst.61.827

• C.M. Poskitt and D. Plump
  Hoare-Style Verification of Graph Programs
  Fundamenta Informaticae 118(1-2):135-175, 2012.
  doi: 10.3233/FI-2012-708

• C.M. Poskitt and D. Plump
  A Hoare Calculus for Graph Programs
  Proc. International Conference on Graph Transformation (ICGT 2010), Lecture Notes in Computer Science 6372, pages 139-154. Springer, 2010.
  doi: 10.1007/978-3-642-15928-2_10

---

Checking Graph Programs for Confluence

• I. Hristakiev and D. Plump
  Checking Graph Programs for Confluence
  Software Technologies: Applications and Foundations - STAF 2017 Collocated Workshops, Revised Selected Papers. Lecture Notes in Computer Science 10748, pages 92-108. Springer, 2018.
  doi: 10.1007/978-3-319-74730-9_8

• I. Hristakiev
  Confluence Analysis for a Graph Programming Language
  PhD thesis, University of York, 2017

• I. Hristakiev and D. Plump
  Towards Critical Pair Analysis for the Graph Programming Language GP 2
  Recent Trends in Algebraic Development Techniques (WADT 2016), Revised Selected Papers. Lecture Notes in Computer Science 10644, pages 153-169. Springer, 2017.
  doi: 10.1007/978-3-319-72044-9_11

• I. Hristakiev and D. Plump
  Attributed Graph Transformation via Rule Schemata: Church-Rosser Theorem
  Software Technologies: Applications and Foundations - STAF 2016 Collocated Workshops, Revised Selected Papers. Lecture Notes in Computer Science 9946, pages 145-160. Springer, 2016.
  doi: 10.1007/978-3-319-50230-4_11

• I. Hristakiev and D. Plump
  A Unification Algorithm for GP 2
  Graph Computation Models (GCM 2014), Revised Selected Papers. Electronic Communications of the EASST 71, 17 pages, 2015.
  doi: 10.14279/tuj.eceasst.71.1002.991

• I. Hristakiev and D. Plump
  A Unification Algorithm for GP 2 (Long Version)
  ArXiv e-prints, arXiv:1705.02171, 2017

---

Probabilistic GP 2 and Evolutionary Algorithms

• T. Atkinson
  Evolving Graphs by Graph Programming
  PhD thesis, University of York, 2019.

• T. Atkinson, D. Plump and S. Stepney
  Evolving Graphs with Semantic Neutral Drift
  Natural Computing 20(1):127-143. Springer, 2021.

• T. Atkinson, D. Plump and S. Stepney
  Horizontal Gene Transfer for Recombining Graphs
  Genetic Programming and Evolvable Machines 21:321-347. Springer, 2020.

• T. Atkinson, D. Plump and S. Stepney
  Evolving Graphs with Horizontal Gene Transfer
  Proc. Genetic and Evolutionary Computation Conference (GECCO 2019), pages 968-976. ACM, 2019.
  doi: 10.1145/3321707.3321788

• T. Atkinson, D. Plump and S. Stepney
  Probabilistic Graph Programs for Randomised and Evolutionary Algorithms
  Proc. International Conference on Graph Transformation (ICGT 2018). Lecture Notes in Computer Science 10887, pages 63-78. Springer, 2018.
  doi: 10.1007/978-3-319-92991-0_5

• T. Atkinson, D. Plump and S. Stepney
  Evolving Graphs by Graph Programming
  Proc. European Conference on Genetic Programming (EuroGP 2018). Lecture Notes in Computer Science 10781, pages 35-51. Springer, 2018.
  doi: 10.1007/978-3-319-77553-1_3

---

Case Studies in Graph Programming

• D. Plump, R. Suri and A. Singh
  Minimizing Finite Automata with Graph Programs
  Graph Computation Models (GCM 2010), Revised Selected Papers. Electronic Communications of the EASST 39, 15 pages, 2011.
  doi: 10.14279/tuj.eceasst.39.658

• G. Taentzer, E. Biermann, D. Bisztray, B. Bohnet, I. Boneva, A. Boronat, L. Geiger, R. Geiss, A. Horvath, O. Kniemeyer, T. Mens, B. Ness, D. Plump and T. Vajk
  Generation of Sierpinski Triangles: A Case Study for Graph Transformation Tools
  Applications of Graph Transformation with Industrial Relevance (AGTIVE 2007), Revised Selected and Invited Papers. Lecture Notes in Computer Science 5088, pages 514-539. Springer, 2008.
  doi: 10.1007/978-3-540-89020-1_35