Subset space logic with arbitrary announcements

Philippe Balbiani (1, 2) , Hans van Ditmarsch (3, 4) , Andrey Kudinov (5)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
2 CNRS - Centre National de la Recherche Scientifique
3 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
4 IMSc - Institute of Mathematical Sciences [Chennai]
5 MIPT - Moscow Institute of Physics and Technology [Moscow]

In this paper we introduce public announcements to Subset Space Logic (SSL). In order to do this we have to change the original semantics for SSL a little and consider a weaker version of SSL without the cross axiom. We present an axiomatization, prove completeness and show that this logic is PSPACE-complete. Finally, we add the arbitrary announcement modality which expresses “true after any announcement”, prove several semantic results, and show completeness for a Hilbert-style axiomatization of this logic.

Mots clés: Subset Space Logic (SSL)

Domaines: Intelligence artificielle [cs.AI]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]; Informatique et langage [cs.CL]

Philippe Balbiani, Hans van Ditmarsch, Andrey Kudinov. Subset space logic with arbitrary announcements. 5th Indian Conference on Logics and its Applications (ICLA 2013), Jan 2013, Chennai, India. pp.233-244, ⟨10.1007/978-3-642-36039-8_21⟩. ⟨hal-01202518⟩