Novembre 2019 — Intelligence Artificielle

« Dynamic epistemic logic for distributed computing – asynchrony and concurrency » par H. van Ditmarsch (LORIA)
« Non-normal modal logics: from models to proofs » par T. Dalmonte (LIS)
« Consistency Measures, Inconsistency Measures, and Mix Measures  » par V. Risch (LIS)

Orateur : Tiziano Dalmonte, LIS
Titre : Non-normal modal logics: from models to proofs
Résumé : Modal logics are applied in many different contexts, such as epistemic, deontic or temporal reasoning, and many others. In some of these contexts, the minimal normal modal logic K leads to counter-intuitive conclusions, such as the problem of logical omniscience or the problem of conflicting obligations, and gives rise to several paradoxes (Ross paradox, the paradox of gentle murder, …). For this reason, weaker modal logics — called non-normal – are considered. Non-normal modal logics are traditionally characterised by a possible world semantics with a neighbourhood function. In this talk I present an alternative semantics which is more natural for systems lacking monotonicity. I also present some new proof systems which have ‘good’ properties, moreover they provide a decision procedure of optimal complexity and allow one to construct countermodels for non-valid formulas. In the final part I present some open problems.

Orateur : Vincent Risch (LIS)
Titre : Consistency Measures, Inconsistency Measures, and Mix Measures (Preliminary Report)
Résumé : En collaboration avec Philippe Besnard Abstract: We give some insight into a preliminary attempt at investigating a notion of consistency measures. These would provide a consistency degree for any finite collection of logical formulas, on a par with the well-known notion of inconsistency measures, that aim at assigning degrees of inconsistency to finite sets of logical formulas. We first propose a basic set of postulates for consistency measures. We look at a couple of relationships with inconsistency measures. We even lay grounds for a formal duality between these two domains. Lastly, we have a look at what would be a mix measure, that is, a measure that gives a degree, on the same scale, for consistency (positive values) and inconsistency (negative values). We also mention supermodels, as defined by Ginsberg et al., as well as a theory that can be regarded as a generalization of super-models, namely morpho-logics.

Orateur : Hans van Ditmarsch (LORIA)
Titre : Dynamic epistemic logic for distributed computing – asynchrony and concurrency
Résumé : We will present some recent work on asynchrony and concurrency in dynamic epistemic logics (DEL), building on foundations in distributed computing and temporal epistemic logics. Asynchrony can be modelled by reasoning over histories of actions of different length. How to do this in DEL was proposed by [Dégremont, Löwe, Witzel: TARK 2011]. By equivalence relations on protocol-generated forests along different depths of trees, they can identify action histories of different length. More or less strongly related to DEL this was also considered for: gossip protocols [Apt, Grossi, vd Hoek, TARK 2015], logic puzzles [vD, van Eijck, Wu: KR 2010], and for the immediate snapshot algorithm in distributed computing [Goubault, Ledent, Rajsbaum: GandALF 2018]. We will present the last in some detail: Kripke models and action models can be represented as simplicial complexes. Dynamic epistemic logic can then be interpreted on such complexes. From the perspective of dynamic epistemic logic, a further departure towards distributed computing and asynchrony is to distinguish the sending and receiving of messages, such as the making versus hearing of announcements. Recent proposals are [Knight, Maubert, Schwarzentruber; MSCS 2019] and [Balbiani, vD, Fernandez Gonzalez; ArXiV 2019] (SR 2017). From the latter we will present asynchronous announcement logic. Its axiomatization resembles that of public announcement logic, and the dynamic modalities can also be eliminated. Further research is on (what is known as) concurrent common knowledge. Finally, how do we model concurrency in DEL? Both true concurrency and intersection concurrency are conceivable. We recall some older work in the area: [vD, vd Hoek, Kooi: AAMAS 2003] and [van Eijck, Sietsma, Wang: JANCL 2011]. The Muddy Children Problem is a joy forever: the action of three muddy children not stepping forward because none of them know whether they are muddy, is always modelled as the public announcement of a conjunction with three conjuncts. Should this not be a concurrent action with three components?