Reasoning about knowledge on regular expressions is 2EXPTIME-complete
Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber · 2025
Read Reasoning about knowledge on regular expressions is 2EXPTIME-complete by Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-09784.txt.
Introduction
Avijeet Ghosh and co-authors published a research paper in 2025 settling how hard it is to reason in a logic where agents learn from public observations described by regular expressions. In this logic, each state lists the observations an agent expects, and knowledge updates as real observations arrive and match or break those expectations. Such logics underpin planning for teams of agents.
The team proves that deciding whether a statement in this logic can ever hold takes doubly exponential time in the worst case, and that this bound is tight. The result completes the complexity map for the logic. Planners who use it now know the true cost of perfect reasoning in it.
Catalog record
| CREATOR | Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-09784
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reasoning about knowledge on regular expressions is 2EXPTIME-complete Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber 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 ( 𝖯𝖮𝖫 \mathsf{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 𝖯𝖮𝖫 \mathsf{POL} is 2EXPTIME-complete. K eywords Public observation logic \cdot Propositional Dynamic Logic \cdot Satisfiability problem \cdot Complexity 1 Introduction Intelligent artificial agents are being used for performing various tasks including planning and scheduling in real life, from simple to more complicated ones. For example, a robot may try to move from a point to another by overcoming certain hurdles. Or, it may try to keep an eye over the surroundings without other agents knowing about it. Accomplishing a goal in such surveillance activities may involve the robot’s knowledge about other agents’ knowledge. Automated planning [ 1 ] is a branch of study in multi-agent systems that involves deciding whether a sequence or plan of actions exists to attain some goal. An extension of such planning studies is termed as epistemic planning [ 2 ] , where the goal, like in the case of surveillance robot, involves knowledge of multiple agents. Reasoning about knowledge using logical systems has been studied extensively in the domain of modal logic [ 3 ] , more specifically using epistemic logic [ 4 ] . In addition, reasoning about the knowledge dynamics of agents has been studied using dynamic epistemic logic ( \mathsf{DEL} ) [ 5 ] , among others. Evidently, a popular approach in epistemic planning is the use of model-checking problem in \mathsf{DEL} [ 2 ] . However, this problem turns out to be undecidable when one considers finite iterations of such actions in \mathsf{DEL} [ 6 ] . Moreover, it is shown that for the general epistemic planning tasks, the plan existence problem is already undecidable with two agents. Public observation logic ( \mathsf{POL} ) [ 7 ] deals with expected observations (actions) that are associated with each state in an epistemic model [ 4 ] , and are represented by regular expressions. The model gets updated depending on the matching of actual and expected observations, and accordingly, agents’ knowledge gets updated as well. This dynamic behavior based on some sequence (finite iteration) of observations inherently makes this setting useful in reasoning about various concepts involving knowledge and actions, for example, epistemic planning. In [ 8 ] , we show that public announcement logic ( \mathsf{PAL} ) with propositional announcements is closely related to the word fragment of \mathsf{POL}, where the regular expressions describing observations are only in the word form. In this sense, \mathsf{POL} can be considered as a dynamic logic-like extension of \mathsf{PAL} , taking iteration of the Boolean announcements under its wings. Thus, it is worthwhile to check whether \mathsf{POL} is decidable, since \mathsf{PAL} with iterated announcements is undecidable [ 9 ] . Note that the decidability [ 10 ] of arbitrary \mathsf{PAL} with Boolean announcements ( \mathsf{BAPAL} ) provides a push towards an affirmative response to our query. Before moving forward, let us provide a scenario that can be modeled by \mathsf{POL}. Example 1 . Consider a surveillance drone hovering over the boundary zone between two territories, T_{1} and T_{2} , say, in conflict with each other. Suppose the drone is deployed by T_{1} , and if it is detected in the airspace of T_{2} , it might get destroyed. How would the drone differentiate between the two territories so that it can restrict itself from entering T_{2} ? According to its expectations based on the vegetation in the area, if it observes the sequence of (spruce ∗ -pine ∗ -cedar-fir ∗ ) ∗ ( \ast denotes the continuance of such sequences), it would know that it is in area T_{1} , while if it observes (spruce ∗ -pine ∗ -larch-fir ∗ ) {}^{\ast}, it would know that it is in T_{2} . With regard to the computational behavior of \mathsf{POL}, we explored the complexity of the model-checking problem for \mathsf{POL} in [ 11 ] . In addition, we investigated the satisfiability problem for the star-free fragment of \mathsf{POL} in [ 8 ] , where the observations comprise of star-free regular expressions. In this work, we complete this study by providing an answer to the remaining open problem concerning the decidability of full \mathsf{POL}. We show that the satisfiability problem of \mathsf{POL} (with Kleene star) is 2EXPTIME-complete, in contrast to \mathsf{PAL} with iterated announcements, making it a more viable option for modelling planning and related problems. The techniques used in our proofs may be of a more general interest. For the upper bound, we start with the usual filtration argument [ 3 ] - if a formula is satisfiable then it is satisfiable in a model of exponential size. Although filtration is usually sufficient to prove decidability, for \mathsf{POL} this is not the case, as the expected observations associated with each state in a model may be arbitrary (Section 3 ). We characterize satisfiability in terms of a finite syntactic structure defined by Hintikka sets [ 12 ] , which we call a bubble transition structure . We provide a correspondence between the expected observations and the corresponding automata (Section 4 ) to facilitate our study. Then in exponential time, we reduce the satisfiability problem of deterministic propositional dynamic logic ( \mathsf{DPDL} ) to that of \mathsf{POL} by encoding the constraints on the epistemic structures by propositional theories (Section 5 ). For the lower bound, we encode a superposition of three same configurations of a Turing machine in the leaves of a \mathsf{POL} model considered as a full binary tree (Section 6 ). Without further ado, let us start by recalling \mathsf{POL} . 2 Public Observation Logic To begin with, we provide a brief overview of Public Observation Logic [ 7 ] . Let \mathcal{P} be a countable set of propositional letters, Ag be a finite set of agents, and \Sigma be a finite alphabet of atomic actions/observations. We now introduce observation expressions as follows: Definition 2 (Observation Expression) . Given a finite set of observations \Sigma , observation expressions are defined recursively as: \pi:=\emptyset\ \ |\ \ a\ \ |\ \ \pi+\pi\ \ |\ \ \pi;\pi\ \ |\ \ \pi^{\star}, with a\in\Sigma . Note that an observation expression \pi is a regular expression, and \mathcal{L}(\pi) denotes the language corresponding to the regular expression \pi . We use these observation expressions to describe observations within formulas (cf. Definition 3 ) as well as expected observations at states in a model (cf. Definition 4 ). In the surveillance example, an observation may be spruce-pine-cedar-fir-spruce (abbreviated as \mathit{spcfs} ) or spruce-pine-larch-fir-spruce (abbreviated as \mathit{splfs} ), among others. Let us now describe the language of \mathsf{POL}. Definition 3 ( \mathsf{POL} Syntax) . The language of \mathsf{POL} can