Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915444266369024 |
|---|---|
| author | Ghosh, Avijeet Ghosh, Sujata Schwarzentruber, François |
| author_facet | Ghosh, Avijeet Ghosh, Sujata Schwarzentruber, François |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09784 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete Ghosh, Avijeet Ghosh, Sujata Schwarzentruber, François Artificial Intelligence Computational Complexity Logic in Computer Science 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. |
| title | Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete |
| topic | Artificial Intelligence Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2508.09784 |