Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures

DOI10.1016/j.jlamp.2014.08.003zbMath1329.68062OpenAlexW2055560858WikidataQ114851603 ScholiaQ114851603MaRDI QIDQ2347907

Rudolf Berghammer, Sebastian Fischer

Publication date: 10 June 2015

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jlamp.2014.08.003

zbMATH Keywords

relation algebradirected graphsHaskellfunctional programmingrectanglereflexive-transitive closure

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Logical aspects of ?ukasiewicz and Post algebras (03G20)

Related Items

Stone Relation Algebras ⋮ Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm ⋮ Relational characterisations of paths ⋮ Verifying minimum spanning tree algorithms with Stone relation algebras ⋮ An algebraic framework for minimum spanning tree problems

Uses Software

• RelView
• Haskell
• TituRel
• Z
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing representatives
• Fixed-point calculus
• Deriving relational programs for computing kernels by reconstructing a proof of Richardson's theorem
• Relational depth-first-search with applications
• Two graph algorithms derived
• Deriving a class of layer-oriented graph algorithms
• Efficient transitive closure of sparse matrices over closed semirings
• Gaussian elimination is not optimal
• Inductive graphs and functional graph algorithms
• Implementing Relational Specifications in a Constraint Functional Logic Language
• Simple Rectangle-Based Functional Programs for Computing Reflexive-Transitive Closures
• Using Relations to Develop a Haskell Program for Computing Maximum Bipartite Matchings
• A Functional, Successor List Based Version of Warshall’s Algorithm with Applications
• Rectangles, Fringes, and Inverses
• On Automated Program Construction and Verification
• New Bounds on the Complexity of the Shortest Path Problem
• The integration of functions into logic programming: From theory to practice
• Functional programming with graphs
• Automated Verification of Relational While-Programs
• Semigroupoid Interfaces for Relation-Algebraic Programming in Haskell
• Computer Algebra in Scientific Computing
• A Theorem on Boolean Matrices
• The algebraic structure of transitive closure and its application to attribute type signatures

This page was built for publication: Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures