Back to search

University of York

Confluence Analysis for a Graph Programming Language

Abstract

dc:description.abstract

GP 2 is a high-level domain-specific language for programming with graphs. Users write a set of graph transformation rules and organise them with imperative-style control constructs to perform a desired computation on an input graph. As rule selection and matching are non-deterministic, there might be different graphs resulting from program execution. Confluence is a property that establishes the global determinism of a computation despite possible local non-determinism. Conventional confluence analysis is done via so-called critical pairs, which are conflicts in minimal context. A key challenge is extending critical pairs to the setting of GP 2. This thesis concerns the development of confluence analysis for GP 2. First, we extend the notion of conflict to GP 2 rules, and prove that non-conflicting rule applications commute. Second, we define symbolic critical pairs and establish their properties, namely that there are only finitely many of them and that they represent all possible conflicts. We give an effective procedure for their construction. Third, we solve the problem of unifying GP 2 list expressions, which arises during the construction of critical pairs, by giving a unification procedure which terminates with a finite and complete set of unifiers (under certain restrictions). Last but not least, we specify a confluence analysis algorithm based on symbolic critical pairs, and show its soundness by proving the Local Confluence Theorem. Several existing programs are analysed for confluence to demonstrate how the analysis handles several GP 2 features at the same time, and to demonstrate the merit of the used techniques.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hristakiev, Ivaylo
Advisor dc:contributor.advisor
  • Plump, Detlef

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

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

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

Hristakiev, Ivaylo. Confluence Analysis for a Graph Programming Language. doctoral thesis, University of York, 2018.