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 -