Counting and Computing Join-Endomorphisms in Lattices
| Autor: | Santiago Quintero, Frank D. Valencia, Camilo Rueda, Sergio Ramírez |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Relational and Algebraic Methods in Computer Science ISBN: 9783030435196 RAMiCS |
| Popis: | Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set \({\mathcal {E}}(L)\) of all join-endomorphisms of a given finite lattice \(L\). In particular, we show that when \(L\) is \(\mathbf {M}_n\), the discrete order of n elements extended with top and bottom, \(| {\mathcal {E}}(L) | =n!{\mathcal L}_{n}(-1)+(n+1)^2\) where \({\mathcal L}_{n}(x)\) is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n and a set \(S\subseteq {\mathcal {E}}(L)\) of size m, find the greatest lower bound Open image in new window . The join-endomorphism Open image in new window 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+ m\log {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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|