License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.3
URN: urn:nbn:de:0030-drops-85382
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8538/
Go to the corresponding LIPIcs Volume Portal

Pous, Damien

On the Positive Calculus of Relations with Transitive Closure

pdf-format:
LIPIcs-STACS-2018-3.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{pous:LIPIcs:2018:8538,
  author =	{Damien Pous},
  title =	{{On the Positive Calculus of Relations with Transitive Closure}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8538},
  URN =		{urn:nbn:de:0030-drops-85382},
  doi =		{10.4230/LIPIcs.STACS.2018.3},
  annote =	{Keywords: Relation Algebra, Kleene Algebra, Allegories, Automata, Graphs}
}

Keywords: Relation Algebra, Kleene Algebra, Allegories, Automata, Graphs
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI