www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/25325

Title: The primitivity of operators in the algebra of binary relations under conjunctions of containments
Authors: Surinx, Dimitri
Van den Bussche, Jan
Van Gucht, Dirk
Issue Date: 2017
Publisher: IEEE
Citation: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, IEEE,
Abstract: The algebra of binary relations provides union and composition as basic operators, with the empty set as neutral element for union and the identity relation as neutral element for composition. The basic algebra can be enriched with additional features. We consider the diversity relation, the full relation, intersection, set difference, projection, coprojection, converse, and transitive closure. It is customary to express boolean queries on binary relational structures as finite conjunctions of containments. We investigate which features are primitive in this setting, in the sense that omitting the feature would allow strictly less boolean queries to be expressible. Our main result is that, modulo a finite list of elementary interdependencies among the features, every feature is indeed primitive.
URI: http://hdl.handle.net/1942/25325
DOI: 10.1109/LICS.2017.8005122
ISBN: 9781509030194
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Peer-reviewed author version284.98 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.