25 September 2023, 10:30-11:30.
ENS, room S16.
Complexity Study of Reasoning about Knowledge and Public Observations
Abstract: This talk explores the model checking and satisfiability problems in logical systems for reasoning about knowledge and observations of intelligent agents and their interactions. We examine the foundations laid by Kripke and Hintikka, which paved the way towards the development of their dynamic counterparts, e.g., Public announcement logic, and its extensions like Dynamic epistemic logic and Public observation logic. Complexity studies for these logics stem from similar studies in temporal logics initiated by Halpern and Vardi, among others.
More specifically, we focus on Public observation logic and analyze its model checking and satisfiability problems. By investigating these problems, we uncover insights into effective and efficient reasoning about knowledge in multi-agent scenarios. Moreover, we explore how these insights can be applied in solving standard problems in relevant domains like planning.
