Implicit Representation of Relations
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Implicit Representation of Relations. / Glončák, Vladan; Munkstrup, Jarl Emil Erla; Grue Simonsen, Jakob.
I: Theory of Computing Systems, Bind 67, Nr. 6, 2023, s. 1156-1196.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Implicit Representation of Relations
AU - Glončák, Vladan
AU - Munkstrup, Jarl Emil Erla
AU - Grue Simonsen, Jakob
N1 - Publisher Copyright: © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023
Y1 - 2023
N2 - We consider implicit representation of an arbitrary family of relations on finite sets. We derive upper and lower bounds for the general cases and for a number of restricted subfamilies, in particular for sparse and symmetric relations, and for relations first-order definable from families for which labeling schemes are already known. Our work extends existing work on implicit representation of graphs in two ways: (i) the known upper and lower bounds for many standard families of graphs are special cases of the results we derive; (ii) we allow families of relations to relate elements on both distinct sets and on multiple copies of the same set, and for different relations in the same family to have different arities, and to be defined on distinct or overlapping sets. The present paper is the first to study bounds on the size of labeling schemes for relations (including graphs) defined from existing relations using basic operations such as first-order logic. The techniques used to prove new results in this setting may be of independent interest.
AB - We consider implicit representation of an arbitrary family of relations on finite sets. We derive upper and lower bounds for the general cases and for a number of restricted subfamilies, in particular for sparse and symmetric relations, and for relations first-order definable from families for which labeling schemes are already known. Our work extends existing work on implicit representation of graphs in two ways: (i) the known upper and lower bounds for many standard families of graphs are special cases of the results we derive; (ii) we allow families of relations to relate elements on both distinct sets and on multiple copies of the same set, and for different relations in the same family to have different arities, and to be defined on distinct or overlapping sets. The present paper is the first to study bounds on the size of labeling schemes for relations (including graphs) defined from existing relations using basic operations such as first-order logic. The techniques used to prove new results in this setting may be of independent interest.
KW - First-order logic
KW - Implicit representation
KW - Labeling schemes
U2 - 10.1007/s00224-023-10141-z
DO - 10.1007/s00224-023-10141-z
M3 - Journal article
AN - SCOPUS:85167928151
VL - 67
SP - 1156
EP - 1196
JO - Theory of Computing Systems
JF - Theory of Computing Systems
SN - 1432-4350
IS - 6
ER -
ID: 364501177