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 |
