# On verifying expectations and observations of intelligent agents

arXiv: https://arxiv.org/abs/2205.00784 · HTML: https://mlsanity.com/paper/2205.00784/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 43 references that are in the map.
- First posted on arXiv 2 May 2022.

## Builds on (most cited first, 4 of 4)

- [Efficient Multi-agent Epistemic Planning: Teaching Planners About Nested Belief](https://mlsanity.com/paper/2110.02480/) (2021)
- [Information and Computation](https://mlsanity.com/paper/1304.1428/) (2013)
- [On the Complexity of Dynamic Epistemic Logic](https://mlsanity.com/paper/1310.6406/) (2013)
- [Mathematical Logic in Computer Science](https://mlsanity.com/paper/1802.03292/) (2018)

## Built on by (most cited first, 2 of 2)

- [On simple expectations and observations of intelligent agents: A complexity study](https://mlsanity.com/paper/2306.02769/) (2023)
- [Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete](https://mlsanity.com/paper/2508.09784/) (2025)

## Abstract (arXiv)

Public observation logic (POL) is a variant of dynamic epistemic logic to reason about agent expectations and agent observations. Agents have certain expectations, regarding the situation at hand, that are actuated by the relevant protocols, and they eliminate possible worlds in which their expectations do not match with their observations. In this work, we investigate the computational complexity of the model checking problem for POL and prove its PSPACE-completeness. We also study various syntactic fragments of POL. We exemplify the applicability of POL model checking in verifying different characteristics and features of an interactive system with respect to the distinct expectations and (matching) observations of the system. Finally, we provide a discussion on the implementation of the model checking algorithms.