TY - GEN

T1 - Counting and Computing Join-Endomorphisms in Lattices

AU - Quintero, Santiago

AU - Ramirez, Sergio

AU - Rueda, Camilo

AU - Valencia, Frank

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

N2 - Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set of all join-endomorphisms of a given finite lattice. In particular, we show that when is, the discrete order of n elements extended with top and bottom, where is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n and a set of size m, find the greatest lower bound. The join-endomorphism has meaningful interpretations in epistemic logic, distributed systems, and Aumann structures. We show that this problem can be solved with worst-case time complexity in for powerset lattices, for lattices of sets, and for arbitrary lattices. The complexity is expressed in terms of the basic binary lattice operations performed by the algorithm.

AB - Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set of all join-endomorphisms of a given finite lattice. In particular, we show that when is, the discrete order of n elements extended with top and bottom, where is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n and a set of size m, find the greatest lower bound. The join-endomorphism has meaningful interpretations in epistemic logic, distributed systems, and Aumann structures. We show that this problem can be solved with worst-case time complexity in for powerset lattices, for lattices of sets, and for arbitrary lattices. The complexity is expressed in terms of the basic binary lattice operations performed by the algorithm.

KW - Join-endomorphisms

KW - Lattice algorithms

KW - Lattice cardinality

UR - http://www.scopus.com/inward/record.url?scp=85083999465&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-43520-2_16

DO - 10.1007/978-3-030-43520-2_16

M3 - Conference contribution

AN - SCOPUS:85083999465

SN - 9783030435196

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 269

BT - Relational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Proceedings

A2 - Fahrenberg, Uli

A2 - Jipsen, Peter

A2 - Winter, Michael

PB - Springer

T2 - 18th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2020

Y2 - 8 April 2020 through 11 April 2020

ER -