2026-07-23T05:51:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8538 2024-03-06T10:42:15Z ddc:004 open_access

On the Positive Calculus of Relations with Transitive Closure Pous, Damien Relation Algebra Kleene Algebra Allegories Automata Graphs Binary relations are such a basic object that they appear in many places in mathematics and computer science. For instance, when dealing with graphs, program semantics, or termination guarantees, binary relations are always used at some point. In this survey, we focus on the relations themselves, and we consider algebraic and algorithmic questions. On the algebraic side, we want to understand and characterise the laws governing the behaviour of the following standard operations on relations: union, intersection, composition, converse, and reflexive-transitive closure. On the algorithmic side, we look for decision procedures for equality or inequality of relations. After having formally defined the calculus of relations, we recall the existing results about two well-studied fragments of particular importance: Kleene algebras and allegories. Unifying those fragments yields a decidable theory whose axiomatisability remains an open problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Damien Pous 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.3 urn:nbn:de:0030-drops-85382 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode