Tuesday, March 4, 20141:00 pmnote new timeComputational Logic SeminarGraduate Center, rm. 8405New room, for this talk only!

Parameters and the Complexity of Modal Satisfiability

Antonis Achilleos

Graduate Center CUNY

Antonis Achilleos

The complexity of Modal Logic has been extensively studied. Ladner has established most of what are now considered classical results on the matter, determining that most of the usual modal logics are PSPACE-complete. Furthermore, as Chagrov and Rybakov showed, some of these logics remain PSPACE-complete even for their variable-free fragments. We present parameters of modal formulas whose effect on the complexity of modal logic has been studied – like modal depth – and we identify sources of complexity for modal satisfiability.

A big part of this talk is joint work with Michael Lampis and Valia Mitsou.