RLE-based Algorithm for Testing Biorders
- Binary relations with certain properties such as biorders, equivalences or difunctional relations can be represented as particular matrices. In order for these properties to be identified usually a rearrangement of rows and columns is required in order to reshape it into a recognisable normal form. Most algorithms performing these transformations are working on binary matrix representations of the underlying relations. This paper presents an approach to use the RLE-compressed matrix representation as a data structure for storing relations to test whether they are biorders in a hopefully more efficient way.
Document Type: | Conference Object |
---|---|
Language: | English |
Author: | Oliver Lanzerath |
Parent Title (English): | Proceedings of the Student Track of the 15th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS 2015), Braga, Portugal, September 28 - October 1, 2015 |
First Page: | 9 |
Last Page: | 14 |
URL: | https://nbn-resolving.org/urn:nbn:de:0074-1454-4 |
Publisher: | CEUR-WS.org |
Publication year: | 2015 |
Keyword: | RLE-XOR; RLE-permutation; biorder |
Departments, institutes and facilities: | Fachbereich Informatik |
Dewey Decimal Classification (DDC): | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Entry in this database: | 2015/11/11 |