Counting and Computing Join-Endomorphisms in Lattices

Santiago Quintero, Sergio Ramirez, Camilo Rueda, Frank Valencia

Producción: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

2 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaRelational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Proceedings
EditoresUli Fahrenberg, Peter Jipsen, Michael Winter
EditorialSpringer
Páginas253-269
Número de páginas17
ISBN (versión impresa)9783030435196
DOI
EstadoPublicada - 2020
Evento18th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2020 - Palaiseau, Francia
Duración: 08 abr. 202011 abr. 2020

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen12062 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia18th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2020
País/TerritorioFrancia
CiudadPalaiseau
Período08/04/2011/04/20

Huella

Profundice en los temas de investigación de 'Counting and Computing Join-Endomorphisms in Lattices'. En conjunto forman una huella única.

Citar esto