Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge

被引：0

作者：

Pinzon, Carlos ^{[4
]}

Quintero, Santiago ^{[3
]}

Ramirez, Sergio ^{[4
]}

Valencia, Frank ^{[1
,2
]}

机构：

[1] Ecole Polytech Paris, CNRS LIX, Palaiseau, France

[2] Pontificia Univ Javeriana Cali, Cali, Colombia

[3] Ecole Polytech Paris, LIX, Palaiseau, France

[4] INRIA Saclay, Palaiseau, France

来源：

RELATIONAL AND ALGEBRAIC METHODS IN COMPUTER SCIENCE (RAMICS 2021) | 2021年 / 13027卷

关键词：

Distributive knowledge; Join-endomorphims; Lattice algorithms;

D O I：

10.1007/978-3-030-88701-8_25

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let L be a distributive lattice and E(L) be the set of join endomorphisms of L. We consider the problem of finding f Pi(E(L)) g given L and f, g is an element of E(L) as inputs. (1) We show that it can be solved in time O(n) where n = vertical bar L vertical bar. 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 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(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 alpha(n)) where alpha(n) is the inverse of the Ackermann function.

引用

页码：413 / 432

页数：20

共 24 条

[1] Resolving distributed knowledge [J].