Unlike standard modal logics, many dynamic epistemic logics are not closed under uniform substitution. The classic example is Public Announcement Logic (
), an extension of epistemic logic based on the idea of information acquisition as elimination of possibilities. In this paper, we address the open question of whether the set of
, the set of formulas all of whose substitution instances are valid, is decidable. We obtain positive answers for multi-agent
, as well as its extension with relativized common knowledge,
. The conceptual significance of substitution failure is also discussed.