On the Complexity of Multi-agent Justification Logic Under Interacting Justifications

Computational Logic SeminarTuesday, October 1, 20132:00 pmGraduate Center, rm. 3209

Antonis Achilleos

On the Complexity of Multi-agent Justification Logic Under Interacting Justifications

Graduate Center CUNY

We introduce a family of multi-agent justification logics with interactions between the agents’ justifications, by extending and generalizing the two-agent versions of LP introduced by Yavorskaya in 2008. Known concepts and tools from the single-agent justification setting are adjusted for this multiple agent case. We present tableau rules and some preliminary complexity results: in several important cases, the satisfiability problem for these logics remains in the second level of the polynomial hierarchy, while for others it is PSPACE or EXP-hard.

Posted by on September 29th, 2013