{"ID":2882791,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.09784","arxiv_id":"2508.09784","title":"Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete","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.","short_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 anno...","url_abs":"https://arxiv.org/abs/2508.09784","url_pdf":"https://arxiv.org/pdf/2508.09784v1","authors":"[\"Avijeet Ghosh\",\"Sujata Ghosh\",\"François Schwarzentruber\"]","published":"2025-08-13T13:10:16Z","proceeding":"cs.AI","tasks":"[\"cs.AI\",\"cs.CC\",\"cs.LO\"]","methods":"[]","has_code":false}