On difunctions

Backhouse, Roland; Oliveira, José Nuno

Abstract

The notion of a difunction was introduced by Jacques Riguet in 1948. Since then it has played a prominent role in database theory, type theory, program specification and process theory. The theory of difunctions is, however, less known in computing than it perhaps should be. The main purpose of the current paper is to give an account of difunction theory in relation algebra, with the aim of making the topic more mainstream. As is common with many important concepts, there are several different but equivalent characterisations of difunctionality, each with its own strength and practical significance. This paper compares different proofs of the equivalence of the characterisations. A well-known property is that a difunction is a set of completely disjoint rectangles. This property suggests the introduction of the (general) notion of the “core” of a relation; we use this notion to give a novel and, we believe, illuminating characterisation of difunctionality as a bijection between the classes of certain partial equivalence relations.

Citation

Backhouse, R., & Oliveira, J. N. (2023). On difunctions. Journal of Logical and Algebraic Methods in Programming, 134, Article 100878. https://doi.org/10.1016/j.jlamp.2023.100878

• Journal Article Type: Article
• Acceptance Date: May 22, 2023
• Online Publication Date: Jun 27, 2023
• Publication Date: 2023-08
• Deposit Date: Jul 12, 2023
• Publicly Available Date: Jul 12, 2023
• Journal: Journal of Logical and Algebraic Methods in Programming
• Print ISSN: 2352-2208
• Electronic ISSN: 2352-2208
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 134
• Article Number: 100878
• DOI: https://doi.org/10.1016/j.jlamp.2023.100878
• Keywords: Difunction; Relation algebra; Calculational method
• Public URL: https://nottingham-repository.worktribe.com/output/22996648
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S2352220823000329?via%3Dihub
• Additional Information: This article is maintained by: Elsevier; Article Title: On difunctions; Journal Title: Journal of Logical and Algebraic Methods in Programming; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.jlamp.2023.100878; Content Type: article; Copyright: © 2023 The Authors. Published by Elsevier Inc.