Public announcement logic with distributed knowledge: expressivity, completeness and complexity
Public announcement logic with distributed knowledge: expressivity, completeness and complexity
复制标题
分布式知识的公告逻辑：表达性、完整性和复杂性
DOI：
10.1007/s11229-012-0243-3
复制
发表时间：
2011
期刊：
影响因子：
1.5
通讯作者：
Thomas Ågotnes
中科院分区：
文献类型：
--
作者：
Yì Nicholas Wáng;Thomas Ågotnes
虽然具有常识的动态认知逻辑已被广泛研究，但具有分布式知识的动态认知逻辑迄今为止受到的关注却少得多。在本文中，我们研究了具有分布式知识的公告逻辑（）的扩展，特别是它们的表达性、公理化和复杂性。仅使用分布式知识进行扩展并不比具有分布式知识的标准认知逻辑更具表现力。因此，我们的重点是添加公共知识和分布式知识的结果，它比每个组件逻辑更具表现力。我们引入一个公理化，这并不奇怪：它是众所周知的公理的组合。然而，完整性证明并不是微不足道的，它需要同时处理知识、分布式知识、公共知识和公共公告的技术的新颖组合和扩展。我们进一步证明这是可判定的，更准确地说，它是完备的。这个结果也适用于所有联盟（而不仅仅是大联盟）的公共和分布式知识运营商。最后，我们提出了反式互模拟的概念来概括某些结果并更深入地了解证明。
While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics withdistributedknowledge have so far received far less attention. In this paper we study extensions of public announcement logic () with distributed knowledge, in particular their expressivity, axiomatisations and complexity.extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on, the result of adding both common and distributed knowledge to, which is more expressive than each of its component logics. We introduce an axiomatisation of, which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing withknowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show thatis decidable, more precisely that it is-complete. This result also carries over towith common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs.