Back to search

University of York

Verification of graph programs with monadic second-order logic

Abstract

dc:description.abstract

In this thesis, we consider Hoare-style verification for the graph programming language GP 2. In literature, Hoare-style verification for graph programs has been studied by using extensions of nested conditions called E-conditions and M-conditions as assertions. However, E-conditions are only able to express first-order properties of GP 2 graphs, while M-conditions can only express properties of a non-attributed graph. Hence, there is still no logic that can express monadic second-order properties of GP 2 graphs. Moreover, both E-conditions and M-conditions may not be easy to comprehend by programmers used to formal specifications expressed in standard first-order logic. Here, we present an approach to verify GP 2 graph programs with a standard monadic second-order logic. We show how to construct a strongest liberal postcondition with respect to a rule schema and a precondition. We then extend this construction to obtain a strongest liberal postcondition for arbitrary loop-free programs. Also, we show how to construct a precondition expressing successful execution of a loop-free program, and failing execution of a so-called iteration command. These constructions allow us to define a partial proof calculus that can handle a larger class of graph programs than what can be verified by the calculus that uses E-conditions and M-conditions as assertions. Other than partial proof calculus whose assertions are monadic second-order logic, we also define semantic partial proof calculus. Similar calculus has been introduced in literature, but here we update the calculus by considering a GP 2 command that was not considered in existing work.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of York
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wulandari, Gia Septiana
Advisor dc:contributor.advisor
  • Plump, Detlef
ORCID person:identifier.orcid

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.839262

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Wulandari, Gia Septiana. Verification of graph programs with monadic second-order logic. doctoral thesis, University of York, 2021.