@inproceedings{8f3c37fd2aea461ea2eba4c9a1f69329,
title = "Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge",
abstract = "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(n2). (2) We characterize the standard notion of distributed knowledge of a group as the greatest lower bound of the join-endomorphisms 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(n2) 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.",
keywords = "Distributive knowledge, Join-endomorphims, Lattice algorithms",
author = "Carlos Pinz{\'o}n and Santiago Quintero and Sergio Ram{\'i}rez and Frank Valencia",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 19th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2021 ; Conference date: 02-11-2021 Through 05-11-2021",
year = "2021",
month = jan,
day = "1",
doi = "10.1007/978-3-030-88701-8\_25",
language = "English",
isbn = "9783030887001",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "413--432",
editor = "Uli Fahrenberg and Mai Gehrke and Luigi Santocanale and Michael Winter",
booktitle = "Relational and Algebraic Methods in Computer Science - 19th International Conference, RAMiCS 2021, Proceedings",
}