2023/06/05 by Sourav Chakraborty, Avijeet Ghosh, Chakraborty, Sourav +5 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2306.02769
openalex publication_date 2023/06/05 · openalex created_date 2023/06/07 · openalex updated_date 2026/07/28
Public observation logic (POL) reasons about agent expectations and agent observations in various real world situations. The expectations of agents take shape based on certain protocols about the world around and they remove those possible scenarios where their expectations and observations do not match. This in turn influences the epistemic reasoning of these agents. In this work, we study the computational complexity of the satisfaction problems of various fragments of POL. In the process, we also highlight the inevitable link that these fragments have with the well-studied Public announcement logic.