Chennai Mathematical Institute

Seminars




Seminar Announcement
Date: Wednesday, 31 January 2024
Time: 10:30 - 11:30 AM
Venue: Lecture Hall 5
Complexity Study of Reasoning about Knowledge and Public Observations

Avijeet Ghosh
ISI Kolkata.
31-01-24


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.