{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:45:56Z","timestamp":1782535556145,"version":"3.54.5"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032297297","type":"print"},{"value":"9783032297303","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-29730-3_6","type":"book-chapter","created":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:04:41Z","timestamp":1782533081000},"page":"109-128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Formalising and\u00a0Verifying Graph Programs with\u00a0Higher-Order Logic"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5295-3493","authenticated-orcid":false,"given":"Robert","family":"S\u00f6ldner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1148-822X","authenticated-orcid":false,"given":"Detlef","family":"Plump","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,28]]},"reference":[{"issue":"1","key":"6_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s10817-025-09719-8","volume":"69","author":"O Abrahamsson","year":"2025","unstructured":"Abrahamsson, O., Myreen, M.O., Norrish, M., Kanabar, H., Pohjola, J.\u00c5.: Fast, verified computation for HOL ITPs. J. Autom. Reason. 69(1), 7 (2025). https:\/\/doi.org\/10.1007\/s10817-025-09719-8","journal-title":"J. Autom. Reason."},{"key":"6_CR2","doi-asserted-by":"publisher","unstructured":"Barendregt, H.P., Dekkers, W., Statman, R.: Lambda Calculus with Types. Perspectives in Logic. Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139032636","DOI":"10.1017\/CBO9781139032636"},{"key":"6_CR3","doi-asserted-by":"publisher","unstructured":"Campbell, G., Courtehoute, B., Plump, D.: Fast rule-based graph programs. Sci. Comput. Program. 214, 102727 (2022). https:\/\/doi.org\/10.1016\/j.scico.2021.102727. 32 pages","DOI":"10.1016\/j.scico.2021.102727"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"56","DOI":"10.2307\/2266170","volume":"5","author":"A Church","year":"1940","unstructured":"Church, A.: A formulation of the simple theory of types. J. Symb. Log. 5, 56\u201368 (1940)","journal-title":"J. Symb. Log."},{"key":"6_CR5","unstructured":"Courtehoute, B.: Time and space complexity of rule-based graph programs. Ph.D. thesis, University of York (2023)"},{"key":"6_CR6","doi-asserted-by":"publisher","unstructured":"Courtehoute, B., Plump, D.: A small-step operational semantics for GP\u00a02. In: Graph Computation Models (GCM 2021), Revised Selected Papers. Electronic Proceedings in Theoretical Computer Science, vol.\u00a0350, pp. 89\u2013110. Open Publishing Association (2021). https:\/\/doi.org\/10.4204\/EPTCS.350.6","DOI":"10.4204\/EPTCS.350.6"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-45832-8_12","volume-title":"Graph Transformation","author":"A Habel","year":"2002","unstructured":"Habel, A., Plump, D.: Relabelling in graph transformation. In: Corradini, A., Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2002. LNCS, vol. 2505, pp. 135\u2013147. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45832-8_12"},{"key":"6_CR8","doi-asserted-by":"publisher","unstructured":"Klein, G., et al.: seL4: formal verification of an OS kernel. In: Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (SOSP 2009), pp. 207\u2013220. ACM (2009). https:\/\/doi.org\/10.1145\/1629575.1629596","DOI":"10.1145\/1629575.1629596"},{"issue":"7","key":"6_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1538788.1538814","volume":"52","author":"X Leroy","year":"2009","unstructured":"Leroy, X.: Formal verification of a realistic compiler. Commun. ACM 52(7), 107\u2013115 (2009). https:\/\/doi.org\/10.1145\/1538788.1538814","journal-title":"Commun. ACM"},{"key":"6_CR10","doi-asserted-by":"publisher","unstructured":"Myreen, M.O., Carneiro, M.: GOL in GOL in HOL: verified circuits in Conway\u2019s Game of Life. In: 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0352, pp. 25:1\u201325:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPIcs.ITP.2025.25","DOI":"10.4230\/LIPIcs.ITP.2025.25"},{"key":"6_CR11","doi-asserted-by":"publisher","unstructured":"Nipkow, T., Klein, G.: Concrete Semantics with Isabelle\/HOL. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-10542-0","DOI":"10.1007\/978-3-319-10542-0"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s11786-014-0183-z","volume":"9","author":"L Noschinski","year":"2014","unstructured":"Noschinski, L.: A graph library for Isabelle. Math. Comput. Sci. 9(1), 23\u201339 (2014). https:\/\/doi.org\/10.1007\/s11786-014-0183-z","journal-title":"Math. Comput. Sci."},{"key":"6_CR13","unstructured":"Plump, D.: Hypergraph rewriting: critical pairs and undecidability of confluence. In: Term Graph Rewriting: Theory and Practice, chap.\u00a015, pp. 201\u2013213. Wiley (1993). https:\/\/www-users.york.ac.uk\/~djp10\/Papers\/wiley.93.pdf"},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Plump, D.: The design of GP 2. In: Proceedings of Workshop on Reduction Strategies in Rewriting and Programming (WRS 2011). Electronic Proceedings in Theoretical Computer Science, vol.\u00a082, pp. 1\u201316. Open Publishing Association (2012). https:\/\/doi.org\/10.4204\/EPTCS.82.1","DOI":"10.4204\/EPTCS.82.1"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jlamp.2016.12.001","volume":"88","author":"D Plump","year":"2017","unstructured":"Plump, D.: From imperative to rule-based graph programs. J. Log. Algebraic Methods Program. 88, 154\u2013173 (2017). https:\/\/doi.org\/10.1016\/j.jlamp.2016.12.001","journal-title":"J. Log. Algebraic Methods Program."},{"issue":"1\u20132","key":"6_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.3233\/FI-2012-708","volume":"118","author":"CM Poskitt","year":"2012","unstructured":"Poskitt, C.M., Plump, D.: Hoare-style verification of graph programs. Fund. Inform. 118(1\u20132), 135\u2013175 (2012). https:\/\/doi.org\/10.3233\/FI-2012-708","journal-title":"Fund. Inform."},{"key":"6_CR17","doi-asserted-by":"publisher","unstructured":"Poskitt, C.M., Plump, D.: Verifying total correctness of graph programs. In: Graph Computation Models (GCM 2012), Revised Selected Papers. Electronic Communications of the EASST, vol.\u00a061. Berlin Universities Publishing (2013). https:\/\/doi.org\/10.14279\/tuj.eceasst.61.827","DOI":"10.14279\/tuj.eceasst.61.827"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-09108-2_3","volume-title":"Graph Transformation","author":"CM Poskitt","year":"2014","unstructured":"Poskitt, C.M., Plump, D.: Verifying monadic second-order properties of graph programs. In: Giese, H., K\u00f6nig, B. (eds.) ICGT 2014. LNCS, vol. 8571, pp. 33\u201348. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09108-2_3"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"100825","DOI":"10.1016\/j.jlamp.2022.100825","volume":"130","author":"CM Poskitt","year":"2023","unstructured":"Poskitt, C.M., Plump, D.: Monadic second-order incorrectness logic for GP 2. J. Logical Algebraic Methods Program. 130, 100825 (2023). https:\/\/doi.org\/10.1016\/j.jlamp.2022.100825","journal-title":"J. Logical Algebraic Methods Program."},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-540-71067-7_6","volume-title":"Theorem Proving in Higher Order Logics","author":"K Slind","year":"2008","unstructured":"Slind, K., Norrish, M.: A brief overview of HOL4. In: Mohamed, O.A., Mu\u00f1oz, C., Tahar, S. (eds.) TPHOLs 2008. LNCS, vol. 5170, pp. 28\u201332. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-71067-7_6"},{"key":"6_CR21","doi-asserted-by":"publisher","unstructured":"S\u00f6ldner, R., Plump, D.: Formalising the double-pushout approach to graph transformation. Logical Methods Comput. Sci. 19(4), 1\u201342 (2023). https:\/\/doi.org\/10.46298\/lmcs-19(4:20)2023","DOI":"10.46298\/lmcs-19(4:20)2023"},{"issue":"8","key":"6_CR22","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1017\/S096012951800021X","volume":"28","author":"M Strecker","year":"2018","unstructured":"Strecker, M.: Interactive and automated proofs for graph transformations. Math. Struct. Comput. Sci. 28(8), 1333\u20131362 (2018). https:\/\/doi.org\/10.1017\/S096012951800021X","journal-title":"Math. Struct. Comput. Sci."},{"key":"6_CR23","doi-asserted-by":"publisher","unstructured":"Wulandari, G., Plump, D.: Verifying graph programs with first-order logic. In: Graph Computation Models (GCM 2020), Revised Selected Papers. Electronic Proceedings in Theoretical Computer Science, vol.\u00a0330, pp. 181\u2013200. Open Publishing Association (2020). https:\/\/doi.org\/10.4204\/EPTCS.330.11","DOI":"10.4204\/EPTCS.330.11"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-030-78946-6_13","volume-title":"Graph Transformation","author":"GS Wulandari","year":"2021","unstructured":"Wulandari, G.S., Plump, D.: Verifying graph programs with monadic second-order logic. In: Gadducci, F., Kehrer, T. (eds.) ICGT 2021. LNCS, vol. 12741, pp. 240\u2013261. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-78946-6_13"}],"container-title":["Lecture Notes in Computer Science","Graph Transformation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-29730-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:04:52Z","timestamp":1782533092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-29730-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032297297","9783032297303"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-29730-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"28 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"ICGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Graph Transformation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rennes","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"icgt2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/icgt-2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}