Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge

Résumé

Let L be a distributive lattice and E(L) be the set of join endomorphisms of L. We consider the problem of finding f E(L) g given L and f, g ∈ E(L) as inputs. (1) We show that it can be solved in time O(n) where n = |L|. The previous upper bound was O(n^2). (2) We characterize the standard notion of distributed knowledge of a group as the greatest lower bound of the joinendomorphisms representing the knowledge of each member of the group. (3) We show that deciding whether an agent has the distributed knowledge of two other agents can be computed in time O(n^2) where n is the size of the underlying set of states. (4) For the special case of S5 knowledge, we show that it can be decided in time O(nα_n) where α_n is the inverse of the Ackermann function.
Fichier principal
Vignette du fichier
main.pdf (473.81 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 2

Citer

Carlos Pinzón, Santiago Quintero, Sergio Ramírez, Frank D. Valencia. Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge. RAMICS 2021 - Relational and Algebraic Methods in Computer Science, Nov 2021, Marseille, France. pp.413-432. ⟨hal-02422624v2⟩
481 Consultations
268 Téléchargements

Partager

Gmail Facebook X LinkedIn More