License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.33
URN: urn:nbn:de:0030-drops-158434
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15843/
Go to the corresponding LIPIcs Volume Portal

Goubault, Éric ; Ledent, Jérémy ; Rajsbaum, Sergio

A Simplicial Model for KB4_n: Epistemic Logic with Agents That May Die

pdf-format:
LIPIcs-STACS-2022-33.pdf (1.0 MB)

Abstract

The standard semantics of multi-agent epistemic logic S5_n is based on Kripke models whose accessibility relations are reflexive, symmetric and transitive. This one dimensional structure contains implicit higher-dimensional information beyond pairwise interactions, that we formalized as pure simplicial models in a previous work in Information and Computation 2021 [Éric Goubault et al., 2021]. Here we extend the theory to encompass simplicial models that are not necessarily pure. The corresponding class of Kripke models are those where the accessibility relation is symmetric and transitive, but might not be reflexive. Such models correspond to the epistemic logic KB4_n. Impure simplicial models arise in situations where two possible worlds may not have the same set of agents. We illustrate it with distributed computing examples of synchronous systems where processes may crash.

BibTeX - Entry

@InProceedings{goubault_et_al:LIPIcs.STACS.2022.33,
  author =	{Goubault, \'{E}ric and Ledent, J\'{e}r\'{e}my and Rajsbaum, Sergio},
  title =	{{A Simplicial Model for KB4\underlinen: Epistemic Logic with Agents That May Die}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15843},
  URN =		{urn:nbn:de:0030-drops-158434},
  doi =		{10.4230/LIPIcs.STACS.2022.33},
  annote =	{Keywords: Epistemic logic, Simplicial complexes, Distributed computing}
}

Keywords: Epistemic logic, Simplicial complexes, Distributed computing
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI