Schematic Validity in Dynamic Epistemic Logic: Decidability

Wesley H. Holliday, Tomohiro Hoshi, Thomas F. Icard IiiLORI 2011 · DOI

TL;DR

This paper tackles the question of whether the set of "schematic validities" in dynamic epistemic logics (DEL) like Public Announcement Logic (PAL) is decidable. The authors provide a positive answer for multi-agent PAL and its extension with common knowledge (PAL-RC), demonstrating that we can effectively determine if a formula holds universally across all possible substitutions. This is a significant step towards understanding the expressive power and limitations of these logics for reasoning about information change.

What Problem Does This Paper Address?

Dynamic epistemic logics (DEL) are powerful tools for modeling how agents acquire information and how this affects their knowledge and beliefs. A key feature of many DELs, including the widely used Public Announcement Logic (PAL), is their ability to represent information updates through "announcement" operators. However, a curious phenomenon arises: while many formulas are valid in these logics, not all of them remain valid when you substitute arbitrary formulas for their atomic components. This property is called "schematic validity," and logics that fail it are not "closed under uniform substitution."

The paper focuses on the "substitution core" of a logic, which is precisely the set of its schematically valid formulas. The central problem addressed is whether this substitution core is decidable for multi-agent PAL and its extension, PAL-RC. Decidability means there exists an effective procedure (an algorithm) that can determine, for any given formula, whether it belongs to the substitution core. This is crucial for understanding the logical properties of these systems and for developing automated reasoning tools. The authors highlight that this question was an open problem in the field.

Methods

The core of the paper's contribution lies in developing a novel procedure to construct a finite set of substitution instances for any given formula. The strategy is as follows:

  1. Simplification: First, any formula is transformed into an equivalent "simple" formula. Simple formulas are built up from atomic propositions using only negation, knowledge operators, announcement operators applied to atomic propositions, conjunction, and common knowledge operators. This simplification is justified by existing schematic validities.
  2. Substitution Transformation: For a given formula $\phi$ and a substitution $\sigma$, if $\sigma(\phi)$ is falsified in a model $M$ at a world $w$, the authors construct a special substitution $\tau$ and an extended model $N$. This $\tau$ is designed such that $\tau(\phi)$ is also falsified in $N$ at $w$. The construction of $\tau$ involves:
  3. Identifying all atomic propositions $p$ in $\phi$.
  4. For each $p$, defining $\tau(p)$ as a complex formula involving knowledge operators and common knowledge operators (specifically, relativized common knowledge operators $C^a$). These operators are constructed based on the structure of $\phi$ and the specific substitution $\sigma$.
  5. The construction of $\tau$ ensures that the truth conditions of $\tau(\phi)$ in the extended model $N$ mirror the falsity of $\sigma(\phi)$ in the original model $M$.
  6. Finite Model Property: The key insight is that this construction yields a finite set of substitution instances for any given $\phi$. This finiteness arises from the fact that the construction of $\tau$ depends on a finite number of possibilities related to the structure of $\phi$ and the substitution $\sigma$.
  7. Decidability Argument: If a formula $\phi$ is not schematically valid, then there must exist some substitution $\sigma$ and some model $M$ where $\sigma(\phi)$ is false. The procedure described above guarantees that for such a $\sigma$ and $M$, we can construct a $\tau$ and a model $N$ such that $\tau(\phi)$ is also false. Since the set of such $\tau(\phi)$ instances is finite for any given $\phi$, we can check the validity of each instance using the known decidable decision procedures for PAL and PAL-RC. If any of these finite instances are found to be invalid, then $\phi$ is not schematically valid. Conversely, if all instances in this finite set are valid, then $\phi$ is schematically valid.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Substitution Failure is Informative: The paper emphasizes that the failure of schematic validity in DELs is not a bug but a feature that reveals important subtleties about information change. For instance, it highlights how certain principles might not hold for information about agents' own knowledge (as seen in the Moore sentence examples).
  • Constructive Proof of Decidability: The main technical contribution is a constructive method to generate a finite set of substitution instances that are sufficient to test for schematic validity. This moves beyond theoretical existence proofs to provide a practical algorithmic approach.
  • Bridging PAL and PAL-RC: The method is shown to work for both PAL and PAL-RC, demonstrating its generality for a significant class of DELs. The extension to PAL-RC leverages its relativized common knowledge operators.
  • The Role of Atomic Sentences: The paper touches upon the conceptual role of atomic sentences in PAL, suggesting they are often used to represent stable external states rather than arbitrary propositions, which contributes to substitution failure.

Key Results

  • Decidability of Substitution Cores: The paper proves that the substitution cores of multi-agent Public Announcement Logic (PAL) and its extension with relativized common knowledge (PAL-RC) are decidable.
  • Finite Set of Test Instances: For any formula $\phi$ in PAL or PAL-RC, the authors provide a procedure to construct a finite set of substitution instances of $\phi$. If $\phi$ is not schematically valid, at least one instance in this finite set will be falsifiable.

Limitations and Future Work

  • Generalization to Arbitrary Relations: The current work focuses on models with equivalence relations for knowledge. The authors mention that in a follow-up paper [14], they will show how their approach applies to models with arbitrary relations, which is a more general setting for epistemic logic.
  • Uniform Public Announcement Logic (UPAL): The paper hints at presenting axiomatizations of the substitution cores of PAL and PAL-RC within a system called Uniform Public Announcement Logic (UPAL) in future work. UPAL treats atomic sentences as genuine propositional variables, potentially offering a different perspective on substitution.
  • Conceptual Significance of Substitution Failure: While the paper discusses the conceptual significance of substitution failure through examples, further exploration of its implications for modeling and reasoning in specific scenarios could be a future direction.

Summary updated

BibTeX
@inproceedings{holliday2011schematic,
  author = {Wesley H. Holliday and Tomohiro Hoshi and Thomas F. Icard III},
  title = {{Schematic Validity in Dynamic Epistemic Logic: Decidability}},
  booktitle = {LORI},
  year = {2011},
  doi = {10.1007/978-3-642-24130-7\_6},
}
Figure