The undecidability of group announcements
Thomas Ågotnes, Hans van Ditmarsch, Tim French · 2014
This paper addresses and solves the long-standing open prob- lem of whether Group Announcement Logic (GAL) is de- cidable. GAL is a dynamic epistemic logic for reasoning about which states of knowledge a group of agents can make come about by sharing their knowledge, with an operator for quantifying over all truthful public announcements that can be made by the group. We show that the satisfiability prob- lem for the logic is undecidable; it is co-RE complete.