Skip to main content

TS

Cardinality of relations and relational approximation algorithms

Authors

Rudolf Berghammer, Peter Hoefner and Insa Stucke

Christian-Albrechts-Universität zu Kiel

NICTA

UNSW

Abstract

We discuss three specific classes of relations which allow to model the essential constituents of graphs, such as vertices and (directed or undirected) edges. Based on Kawahara's characterisation of the cardinality of relations we then derive fundamental properties on their cardinalities. As main applications of these results, we formally verify four relational programs which implement approximation algorithms by using the assertion-based method and relation-algebraic calculations.

BibTeX Entry

  @article{Berghammer_HS_16,
    doi              = {10.1016/j.jlamp.2015.12.001},
    journal          = {Journal of Logical and Algebraic Methods in Programming},
    author           = {Berghammer, Rudolf and Höfner, Peter and Stucke, Insa},
    number           = {2},
    month            = may,
    volume           = {85},
    year             = {2016},
    title            = {Cardinality of Relations and Relational Approximation Algorithms},
    pages            = {269-286}
  }

Download

Served by Apache on Linux on seL4.