About Me

Abstract:

As an alternative to Kripke models, simplicial complexes are a versatile semantic primitive on which to interpret epistemic logic. Given a set of vertices, a simplicial complex is a downward closed set of subsets, called simplexes, of the vertex set. A maximal simplex is called a facet. Impure simplicial complexes represent that some agents (processes) are dead. It is known that impure simplicial complexes categorically correspond to so-called partial epistemic (Kripke) models. In this contribution, we define a notion of bisimulation to compare impure simplicial complexes and show that it has the Hennessy-Milner property. These results are for a logical language including atoms that express whether agents are alive or dead. Without these atoms no reasonable standard notion of bisimulation exists, as we amply justify by counterexamples, because such a restricted language is insufficiently expressive.

Abstract:

Simplicial complexes are a convenient semantic primitive to reason about processes (agents) communicating with each other in synchronous and asynchronous computation. Impure simplicial complexes distinguish active processes from crashed ones, in other words, agents that are alive from agents that are dead. In order to rule out that dead agents reason about themselves and about other agents, three-valued epistemic semantics have been proposed where, in addition to the usual values true and false, the third value stands for undefined: the knowledge of dead agents is undefined and so are the propositional variables describing their local state. Other semantics for impure complexes are two-valued where a dead agent knows everything. Different choices in designing a semantics produce different three-valued semantics, and also different two-valued semantics. In this work, we categorize the available choices by discounting the bad ones, identifying the equivalent ones, and connecting the non-equivalent ones via a translation. The main result of the paper is identifying the main relevant distinction to be the number of truth values and bridging this difference by means of a novel embedding from three- into two-valued semantics. This translation also enables us to highlight quite fundamental modeling differences underpinning various two- and three-valued approaches in this area of combinatorial topology. In particular, pure complexes can be defined as those invariant under the translation.

Abstract:

Combinatorial topology is used in distributed computing to model concurrency and asynchrony. The basic structure in combinatorial topology is the simplicial complex, a collection of subsets called simplices of a set of vertices, closed under containment. Pure simplicial complexes describe message passing in asynchronous systems where all processes (agents) are alive, whereas impure simplicial complexes describe message passing in synchronous systems where processes may be dead (have crashed). Properties of impure simplicial complexes can be described in a three-valued multi-agent epistemic logic where the third value represents formulae that are undefined, e.g., the knowledge and local propositions of dead agents. In this work we present an axiomatization for the logic of the class of impure complexes and show soundness and completeness. The completeness proof involves the novel construction of the canonical simplicial model and requires a careful manipulation of undefined formulae.

TU Wien

Type: PhD Thesis

Link: Diss_Randrianomentsoa 

Stellenbosch University

Type: Master's thesis

Link: scholar.sun.ac.za/server/api/core/bitstreams/8173895b-41ef-42fc-ba68-d838ef90b717/content 

Logic Algebra and Truth Degrees, Siena, Italy, 21-25 July 202512–16 May 202512–16 May 2025

Type: Extended Abstract

Link: LATD2025 

Logica, 12-16 May 202512–16 May 202512–16 May 2025

Type: Extended Abstract

Link: Logica2025 

Connections between Epistemic Logic and Topology, Amsterdam, Netherlands, October 24-26, 2022

Type: Extended Abstract

Link: easychair.org/cfp/CELT2022 

AIMS South Africa Research Centre Report 2020, page 24-25

Type: Extended Abstract

Link: aims.ac.za/wp-content/uploads/sites/5/2022/02/ARC-Report-2020-FINAL.pdf 

African Institute for Mathematical Sciences, South Africa

Type: Essay

Link: drive.google.com/file/d/1tr-prx0uDDhTiI6xnNJqPqcz4_ridu01/view