Implicit Representation of Relations

Department of Computer Science

Implicit Representation of Relations

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Implicit Representation of Relations. / Glončák, Vladan; Munkstrup, Jarl Emil Erla; Grue Simonsen, Jakob.

In: Theory of Computing Systems, Vol. 67, No. 6, 2023, p. 1156-1196.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Glončák, V, Munkstrup, JEE & Grue Simonsen, J 2023, 'Implicit Representation of Relations', Theory of Computing Systems, vol. 67, no. 6, pp. 1156-1196. https://doi.org/10.1007/s00224-023-10141-z

APA

Glončák, V., Munkstrup, J. E. E., & Grue Simonsen, J. (2023). Implicit Representation of Relations. Theory of Computing Systems, 67(6), 1156-1196. https://doi.org/10.1007/s00224-023-10141-z

Vancouver

Glončák V, Munkstrup JEE, Grue Simonsen J. Implicit Representation of Relations. Theory of Computing Systems. 2023;67(6):1156-1196. https://doi.org/10.1007/s00224-023-10141-z

Author

Glončák, Vladan ; Munkstrup, Jarl Emil Erla ; Grue Simonsen, Jakob. / Implicit Representation of Relations. In: Theory of Computing Systems. 2023 ; Vol. 67, No. 6. pp. 1156-1196.

Bibtex

@article{312f4c3e6fb94134a7636680935cd75a,

title = "Implicit Representation of Relations",

abstract = "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.",

keywords = "First-order logic, Implicit representation, Labeling schemes",

author = "Vladan Glon{\v c}{\'a}k and Munkstrup, {Jarl Emil Erla} and {Grue Simonsen}, Jakob",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

doi = "10.1007/s00224-023-10141-z",

language = "English",

volume = "67",

pages = "1156--1196",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer",

number = "6",

}

RIS

TY - JOUR

T1 - Implicit Representation of Relations

AU - Glončák, Vladan

AU - Munkstrup, Jarl Emil Erla

AU - Grue Simonsen, Jakob

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