Counting and Computing Join-Endomorphisms in Lattices - CNRS - Centre national de la recherche scientifique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Counting and Computing Join-Endomorphisms in Lattices

Résumé

Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set J(L) of all join-endomorphisms of a given finite lattice L. We show that the cardinality of J(L) is sub-exponential, exponential and super-exponential in the size of the lattice for boolean algebras, linear-orders, and arbitrary lattices, respectively. We also study the following problem: Given a lattice L of size n and a set S ⊆ J(L) of size m, find the greatest lower bound in J(L) of S. This 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 O(mn^(log_2 3)) 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.
Fichier principal
Vignette du fichier
main.pdf (503.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02422624 , version 1 (22-12-2019)
hal-02422624 , version 2 (21-01-2020)
hal-02422624 , version 3 (19-12-2023)

Identifiants

  • HAL Id : hal-02422624 , version 1

Citer

Santiago Quintero, Sergio Ramírez, Camilo Rueda, Frank D. Valencia. Counting and Computing Join-Endomorphisms in Lattices. 2019. ⟨hal-02422624v1⟩
481 Consultations
268 Téléchargements

Partager

Gmail Facebook X LinkedIn More