The Undecidability of Group Announcements

This paper addresses and solves the long-standing open problem of whether Group Announcement Logic (GAL) is decidable. 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 problem for the logic is undecidable; it is coRE complete.