A Simplicial Complex Model for Dynamic Epistemic Logic to study Distributed Task Computability
A Simplicial Complex Model for Dynamic Epistemic Logic to study Distributed Task Computability
复制标题
用于研究分布式任务可计算性的动态认知逻辑的简单复杂模型
DOI：
10.4204/eptcs.277.6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Rajsbaum
中科院分区：
文献类型：
--
作者：
É. Goubault;J. Ledent;S. Rajsbaum
多智能体系统的通常认知模型S5n是基于Kripke框架的，Kripke框架是一个图，其边缘用不区分两种状态的智能体标记。我们建议通过考虑二元单纯复杂模型来揭示该结构中隐含的更高维度信息。我们使用动态认知逻辑（DEL）来研究一个认知单纯复形模型在一组智能体相互通信后的变化。我们专注于一个动作模型，表示异步代理的所谓的即时快照通信模式，因为它是分布式可计算性的核心（但我们的设置适用于其他通信模式）。从最初的认知复合体到应用动作模型后的认知复合体，存在拓扑不变量，这些拓扑不变量决定了主体在通信后获得的知识。最后，我们描述了如何分布式任务规范可以建模为一个DEL动作模型，并表明，拓扑不变量确定任务是否是可解的。因此，我们提供了一个桥梁DEL和分布式可计算性的拓扑理论，研究任务的可解性在一个共享的内存或消息传递架构。
The usual epistemic model S5n for a multi-agent system is based on a Kripke frame, which is a graph whose edges are labeled with agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in this structure, by considering a dual, simplicial complex model. We use dynamic epistemic logic (DEL) to study how an epistemic simplicial complex model changes after a set of agents communicate with each other. We concentrate on an action model that represents the so called immediate snapshot communication patterns of asynchronous agents, because it is central to distributed computability (but our setting works for other communication patterns). There are topological invariants preserved from the initial epistemic complex to the one after the action model is applied, which determine the knowledge that the agents gain after communication. Finally, we describe how a distributed task specification can be modeled as a DEL action model, and show that the topological invariants determine whether the task is solvable. We thus provide a bridge between DEL and the topological theory of distributed computability, which studies task solvability in a shared memory or message passing architecture.
影响因子：
1.3
作者：
D. Kozlov
通讯作者：
D. Kozlov