Skip to Main content Skip to Navigation
Conference papers

Counting and Computing Join-Endomorphisms in Lattices

Abstract : 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 for the discrete order of $n$ elements extended with top and bottom, $n!laguerre{n}{-1}+(n+1)^2$ where laguerre${n}{x}$ is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n find the meet of a set S of join-endomorphisms over L of size m. The meet of join-endomorphisms 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 $O(n+ mlog{n} )$ for powerset lattices, $O(mn^2)$ for lattices of sets, and $O(mn + n^3)$ for arbitrary lattices. The complexity is expressed in terms of the basic binary lattice operations performed by the algorithm.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02422624
Contributor : Frank D. Valencia <>
Submitted on : Tuesday, January 21, 2020 - 11:21:26 AM
Last modification on : Monday, February 17, 2020 - 4:32:39 PM
Long-term archiving on: : Wednesday, April 22, 2020 - 4:51:43 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02422624, version 2

Citation

Santiago Quintero, Sergio Ramírez, Camilo Rueda, Frank Valencia. Counting and Computing Join-Endomorphisms in Lattices. RAMICS 2020 - 18th International Conference on Relational and Algebraic Methods in Computer Science, Apr 2020, Paris, France. ⟨hal-02422624v2⟩

Share

Metrics

Record views

115

Files downloads

115