# Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 19 references that are in the map.
- First posted on arXiv 13 Aug 2025.

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

- [A Gentle Introduction to Epistemic Planning: The DEL Approach](https://mlsanity.com/paper/1703.02192/) (2017)
- [Quantifying over Boolean announcements](https://mlsanity.com/paper/1712.05310/) (2017)
- [On verifying expectations and observations of intelligent agents](https://mlsanity.com/paper/2205.00784/) (2022)
- [On simple expectations and observations of intelligent agents: A complexity study](https://mlsanity.com/paper/2306.02769/) (2023)

## Abstract (arXiv)

Logics for reasoning about knowledge and actions have seen many applications in various domains of multi-agent systems, including epistemic planning. Change of knowledge based on observations about the surroundings forms a key aspect in such planning scenarios. Public Observation Logic (POL) is a variant of public announcement logic for reasoning about knowledge that gets updated based on public observations. Each state in an epistemic (Kripke) model is equipped with a set of expected observations. These states evolve as the expectations get matched with the actual observations. In this work, we prove that the satisfiability problem of POL is 2EXPTIME-complete.