Tuesday, October 1, 20132:00 pmComputational Logic SeminarGraduate Center, rm. 3209

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

Antonis Achilleos

Graduate Center CUNY

Antonis Achilleos

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.