Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete

Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber
8/13/2025
cs.AIcs.CCcs.LO

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

78% match2025

Beyond Prediction -- Structuring Epistemic Integrity in Artificial Reasoning Systems

77% match2025

Probabilistic Strategy Logic with Degrees of Observability

77% match2024

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives

77% match1 repo32024

The Equivalence Theorem: First-Class Relationships for Structurally Complete Database Systems

77% match2026

Active Epistemic Control for Query-Efficient Verified Planning

76% match2026

Cite this paper

@article{ghosh2025reasoning,
  title  = {Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete},
  author = {Avijeet Ghosh and Sujata Ghosh and François Schwarzentruber},
  year   = {2025},
  eprint = {2508.09784},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2508.09784v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2508.09784.svg)](https://codeofpaper.com/paper/2508.09784)

Discussion